在不计算其他数的情况下找到第n个置换

在不计算其他数的情况下找到第n个置换

如RickyBobby所述，在考虑排列的字典顺序时，您应该利用阶乘分解来发挥自己的优势。

从实际的角度来看，这是我的看法：

• 执行排序欧几里德师，除非你用阶乘的数字，与开始做

  (n-1)!

  ，

  (n-2)!

  等。
• 将商保持在数组中。该

  i

  个商应该是一个数之间

  0

  和

  n-i-1

  包容性的，其中

  i

  从去

  0

  到

  n-1

  。
• 该数组 是 您的排列。问题在于每个商都不关心先前的值，因此您需要对其进行调整。更明确地说，您需要将每个值递增多少倍，就像先前的值较低或相等一样。

以下C代码应该使您了解其工作原理（

n

是条目数，

i

是排列的索引）：

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 pre   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