PHP: Alphabetical permutation [duplicate]

Question

I have difficult homework:

The list contains alphabetically all strings, which can form the letters A-K. The start of the list looks like this:

ABCDEFGHIJK,
ABCDEFGHIKJ,
ABCDEFGHJIK,
ABCDEFGHJKI, ...

The third string in the list is ABCDEFGHJIK. What is the list n's string?

I have made code to solve problem, but just to somewhere N value between 600 000 - 700 000. When I try to solve task with 700 000, I get 'Fatal error: Allowed memory size of 134217728 bytes exhausted'. And this is the trick of the task, automatic test number 11 is 1.6 million. So there must be a simpler algorithm, but I can not find it with search engine. So what would be algorithm? My code is:

<?php
$number = $_REQUEST['n'];
$lettering = array("A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K");

$counter = $number;
$done = permute($lettering, $counter);

echo $done[$number-1]."<br>";

function permute($array, $counter) {
    global $number;
    if(1 === count($array))
        return $array;
    $result = array();

    foreach($array as $key => $item)
        foreach(permute(array_diff_key($array, array($key => $item)), $counter) as $p){
            $result[] = $item.$p;
            $counter--;
            if($counter == 0) return $result;
        }
    return $result;
}

@MattTimmermans OP is running out of memory; he clearly has to only calculate the permutation at any given N — meowgoesthedog
– meowgoesthedog, Commented Jul 14, 2017 at 12:52
See stackoverflow.com/questions/7918806/…. That computes the nth permutation without forcing you to calculate the preceding ones. — Jim Mischel
– Jim Mischel, Commented Jul 14, 2017 at 13:18
@spug oh, you're right. I didn't read the code. But we've got lots of answers for that here too. — Matt Timmermans
– Matt Timmermans, Commented Jul 14, 2017 at 16:10

meowgoesthedog · Accepted Answer · 2017-07-14 13:34:19Z

Let's take a look at how the permutation function is defined:

def permute(string):
  for each char in string
    sub <- remove char from string
    return concat(char, permute(sub))
end

For a string of length L, the permute function returns an array of length L!. Thus we can see that the list of permutations starting with the char at index i in the string starts at the i*(L-1)! element in the final array.

Thus the find the permutation at index N, we need to iteratively narrow down our search space, by finding the character to append (index given by N / (M - 1)!) and its corresponding substring. We remove this character from the string, append it to the result, and repeat with N <- N % (M - 1)! on the substring (this is the offset index into the list of permutations of this substring).

PHP code:

function factorial($M) {
    $N = 1;
    for (;$M > 0;$M--)
        $N *= $M;
    return $N;
}
function remove_from_str($input, $index) {
   $str1 = substr($input, 0, $index);
   $str2 = substr($input, $index+1);
   return $str1.$str2;
}

function get_permutation($input, $N) {
   $L = strlen($input);
   $result = "";
   for ($M = $L; $M > 0; $M--) {
      $F = factorial($M-1);
      $j = intval(floor($N / $F));
      $result = $result.$input[$j];
      $input = remove_from_str($input, $j);
      $N = $N % $F;
   }
   return $result;
}

Test:

echo get_permutation("ABCDEFGHIJK", 1600000); // Outputs "AFEIGCDJKBH"

(Note: N here starts at 0 rather than 1)

Collectives™ on Stack Overflow

PHP: Alphabetical permutation [duplicate]

I have difficult homework:

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

I have difficult homework:

1 Answer 1

Comments

Linked

Related