php - 在不计算其他排列的情况下找到第 n 个排列

Question

给定一个包含 N 个元素的数组，代表排列原子，是否有这样的算法:

function getNthPermutation( $atoms, $permutation_index, $size )

其中 $atoms 是元素数组，$permutation_index 是排列的索引，$size 是排列的大小.

例如:

$atoms = array( 'A', 'B', 'C' );
// getting third permutation of 2 elements
$perm = getNthPermutation( $atoms, 3, 2 );

echo implode( ', ', $perm )."\n";

将打印:

B, A

在 $permutation_index 之前不计算每个排列？

我听说过一些关于因式排列的事情，但我发现的每个实现都给出了具有相同 V 大小的排列结果，这不是我的情况。

谢谢。

Answer 1

如 RickyBobby 所述，在考虑排列的字典顺序时，您应该使用对您有利的阶乘分解。

从实际的角度来看，我是这样看的:

• 执行一种欧几里德除法，但您使用的是阶乘数，从 (n-1)!、(n-2)! 开始，依此类推上。
• 将商保存在一个数组中。第 i 商应该是介于 0 和 n-i-1 之间的数字，其中 i 来自 0 到 n-1。
• 这个数组是您的排列。问题是每个商都不关心以前的值，所以你需要调整它们。更明确地说，您需要将每个值递增的次数与之前小于或等于的值的次数相同。

下面的 C 代码应该让您了解这是如何工作的(n 是条目数，i 是排列的索引):

/**
 * @param n The number of entries
 * @param i The index of the permutation
 */
void ithPermutation(const int n, int i)
{
   int j, k = 0;
   int *fact = (int *)calloc(n, sizeof(int));
   int *perm = (int *)calloc(n, sizeof(int));

   // compute factorial numbers
   fact[k] = 1;
   while (++k < n)
      fact[k] = fact[k - 1] * k;

   // compute factorial code
   for (k = 0; k < n; ++k)
   {
      perm[k] = i / fact[n - 1 - k];
      i = i % fact[n - 1 - k];
   }

   // readjust values to obtain the permutation
   // start from the end and check if preceding values are lower
   for (k = n - 1; k > 0; --k)
      for (j = k - 1; j >= 0; --j)
         if (perm[j] <= perm[k])
            perm[k]++;

   // print permutation
   for (k = 0; k < n; ++k)
      printf("%d ", perm[k]);
   printf("\n");

   free(fact);
   free(perm);
}

例如，ithPermutation(10, 3628799) 按预期打印十个元素的最后排列:

9 8 7 6 5 4 3 2 1 0