找到第n个排列而不计算其他排列

Question

找到第n个排列而不计算其他排列给定表示置换原子的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