找到第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是排列的索引）：/** &nbsp;*&nbsp;@param&nbsp;n&nbsp;The&nbsp;number&nbsp;of&nbsp;entries &nbsp;*&nbsp;@param&nbsp;i&nbsp;The&nbsp;index&nbsp;of&nbsp;the&nbsp;permutation &nbsp;*/void&nbsp;ithPermutation(const&nbsp;int&nbsp;n,&nbsp;int&nbsp;i){ &nbsp;&nbsp;&nbsp;int&nbsp;j,&nbsp;k&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;int&nbsp;*fact&nbsp;=&nbsp;(int&nbsp;*)calloc(n,&nbsp;sizeof(int)); &nbsp;&nbsp;&nbsp;int&nbsp;*perm&nbsp;=&nbsp;(int&nbsp;*)calloc(n,&nbsp;sizeof(int)); &nbsp;&nbsp;&nbsp;//&nbsp;compute&nbsp;factorial&nbsp;numbers &nbsp;&nbsp;&nbsp;fact[k]&nbsp;=&nbsp;1; &nbsp;&nbsp;&nbsp;while&nbsp;(++k&nbsp;<&nbsp;n) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fact[k]&nbsp;=&nbsp;fact[k&nbsp;-&nbsp;1]&nbsp;*&nbsp;k; &nbsp;&nbsp;&nbsp;//&nbsp;compute&nbsp;factorial&nbsp;code &nbsp;&nbsp;&nbsp;for&nbsp;(k&nbsp;=&nbsp;0;&nbsp;k&nbsp;<&nbsp;n;&nbsp;++k) &nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;perm[k]&nbsp;=&nbsp;i&nbsp;/&nbsp;fact[n&nbsp;-&nbsp;1&nbsp;-&nbsp;k]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;=&nbsp;i&nbsp;%&nbsp;fact[n&nbsp;-&nbsp;1&nbsp;-&nbsp;k]; &nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;//&nbsp;readjust&nbsp;values&nbsp;to&nbsp;obtain&nbsp;the&nbsp;permutation &nbsp;&nbsp;&nbsp;//&nbsp;start&nbsp;from&nbsp;the&nbsp;end&nbsp;and&nbsp;check&nbsp;if&nbsp;preceding&nbsp;values&nbsp;are&nbsp;lower &nbsp;&nbsp;&nbsp;for&nbsp;(k&nbsp;=&nbsp;n&nbsp;-&nbsp;1;&nbsp;k&nbsp;>&nbsp;0;&nbsp;--k) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(j&nbsp;=&nbsp;k&nbsp;-&nbsp;1;&nbsp;j&nbsp;>=&nbsp;0;&nbsp;--j) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(perm[j]&nbsp;<=&nbsp;perm[k]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;perm[k]++; &nbsp;&nbsp;&nbsp;//&nbsp;print&nbsp;permutation &nbsp;&nbsp;&nbsp;for&nbsp;(k&nbsp;=&nbsp;0;&nbsp;k&nbsp;<&nbsp;n;&nbsp;++k) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("%d&nbsp;",&nbsp;perm[k]); &nbsp;&nbsp;&nbsp;printf("\n"); &nbsp;&nbsp;&nbsp;free(fact); &nbsp;&nbsp;&nbsp;free(perm);}例如，ithPermutation(10, 3628799)按预期打印十个元素的最后一个排列：9&nbsp;8&nbsp;7&nbsp;6&nbsp;5&nbsp;4&nbsp;3&nbsp;2&nbsp;1&nbsp;0