PHP:字母排列

Question

<分区>

Answer 1

让我们看一下置换函数是如何定义的:

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

对于长度为 L 的字符串, permute函数返回一个长度为 L! 的数组.因此我们可以看到以 char 开头的排列列表在索引 i在字符串中开始于 i*(L-1)!最终数组中的元素。

因此找到索引 N 处的排列，我们需要通过查找要附加的字符(由 N / (M - 1)! 给出的索引)及其相应的子字符串来迭代缩小我们的搜索空间。我们从字符串中删除这个字符，将其附加到结果中，然后用 N <- N % (M - 1)! 重复在子字符串上(这是该子字符串排列列表中的偏移索引)。

PHP代码:

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

测试:

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

(注意:N 这里从 0 而不是 1 开始)