PHP: Alphabetical permutation

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;
}

https://stackoverflow.com/questions/40752319/algorithm-to-list-unique-permutations-of-string-with-duplicate-letters/40756214#40756214 — Matt Timmermans, Jul 14 '17 at 12:19
@MattTimmermans OP is running out of memory; he clearly has to only calculate the permutation at any given N — meowgoesthedog, Jul 14 '17 at 12:52
See https://stackoverflow.com/questions/7918806/finding-n-th-permutation-without-computing-others. That computes the nth permutation without forcing you to calculate the preceding ones. — Jim Mischel, Jul 14 '17 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, Jul 14 '17 at 16:10

score 1 · Accepted Answer · answered Jul 14 '17 at 13:34

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)

PHP: Alphabetical permutation

I have difficult homework:

1 Answers1