查找第n次置换不计算人 [英] Finding n-th permutation without computing others

问题描述

给定N元素重新presenting置换的原子排列，是有一种算法那样：

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

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

其中， $原子是元素的数组， $ permutation_index 的排列和指数 $尺寸是排列的大小。

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 )."\n";

将打印：

B, A

没有计算每一个排列，直到$ permutation_index？

Without computing every permutation until $permutation_index ?

我听到了一些有关factoradic排列，但每一个实施我已经找到了使作为结果与相同尺寸的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 ）！，等等。
• 保持在一个数组的商数。该我 -th商应当是一个 0 和 NI-1 包，其中我的推移，从 0 到 N-1 。
• 这个数组的是的你的排列。问题是，每个商并不关心previous值，所以你需要对其进行调整。更明确地说，你需要尽可能多的时间每增加值，但是也有一些低于或等于previous值。

• 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 code应该给你如何工作的（ N 的条目数，而我是置换的指标）：

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("\n");

   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屋！