在不计算其他排列的情况下找到第 n 个排列 [英] Finding n-th permutation without computing others

问题描述

给定一个表示置换原子的 N 个元素的数组，是否有这样的算法:

Given an array of N elements representing the permutation atoms, is there an algorithm like that:

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

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

where $atoms is the array of elements, $permutation_index is the index of the permutation and $size is the size of the permutation.

例如:

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

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

会打印:

B, A

不计算每个排列直到 $permutation_index ?

Without computing every permutation until $permutation_index ?

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

I heard something about factoradic permutations, but every implementation i've found gives as result a permutation with the same size of V, which is not my case.

谢谢.

推荐答案

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

As stated by RickyBobby, when considering the lexicographical order of permutations, you should use the factorial decomposition at your advantage.

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

From a practical point of view, this is how I see it:

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

• Perform a sort of Euclidian division, except you do it with factorial numbers, starting with (n-1)!, (n-2)!, and so on.
• Keep the quotients in an array. The i-th quotient should be a number between 0 and n-i-1 inclusive, where i goes from 0 to n-1.
• This array is your permutation. The problem is that each quotient does not care for previous values, so you need to adjust them. More explicitly, you need to increment every value as many times as there are previous values that are lower or equal.

以下 C 代码应该让您了解它的工作原理(n 是条目数，i 是排列的索引):

The following C code should give you an idea of how this works (n is the number of entries, and i is the index of the permutation):

/**
 * @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("
");

   free(fact);
   free(perm);
}

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

For example, ithPermutation(10, 3628799) prints, as expected, the last permutation of ten elements:

9 8 7 6 5 4 3 2 1 0

这篇关于在不计算其他排列的情况下找到第 n 个排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！