find第n个排列而不计算其他排列
给定一个代表置换primefaces的N个元素的数组，是否有这样的algorithm：
function getNthPermutation( $atoms, $permutation_index, $size ) 其中$atoms是元素数组， $permutation_index是$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相同的排列，这不是我的情况。
谢谢。
正如RickyBobby所说，在考虑排列的字典顺序时，你应该使用因子分解。
从实际的angular度来看，这是我的看法：
- 进行一种欧几里德除法，除了用
(n-1)!开始的因子数字来做(n-1)!，(n-2)!， 等等。 - 保持商数在一个数组中。 第
i个商应该是介于0和ni-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
这是一个解决scheme，允许select排列的大小。 例如，除了能够产生10个元素的所有排列之外，它还能够产生10个元素之间的排列的排列。 它也可以排列任意对象的列表，而不仅仅是整数。
这是PHP，但也有JavaScript和Haskell的障碍。
function nth_permutation($atoms, $index, $size) { for ($i = 0; $i < $size; $i++) { $item = $index % count($atoms); $index = floor($index / count($atoms)); $result[] = $atoms[$item]; array_splice($atoms, $item, 1); } return $result; }
用法示例：
for ($i = 0; $i < 6; $i++) { print_r(nth_permutation(['A', 'B', 'C'], $i, 2)); } // => AB, BA, CA, AC, BC, CB
它是如何工作的？
背后有一个非常有趣的想法。 我们来看一下列表A, B, C, D 。 我们可以通过从一副牌中抽取元素来构build一个排列。 最初我们可以画出四个要素之一。 然后是剩下的三个元素之一，等等，直到最后我们什么都没有了。
这是一个可能的select顺序。 从顶部开始，我们走第三条路线，然后是第一条路线，第二条路线，最后是第一条路线。 这就是我们的排列＃13。
想想看，如果给出这一系列的select，你将在algorithm上达到十三个数字。 然后颠倒你的algorithm，这就是你如何从一个整数重build序列。
我们试图find一个将一系列选项打包成一个没有冗余的整数的一般scheme，并将其解包。
一个有趣的scheme称为十进制数字系统。 “27”可以被认为是select10号path中的2号，然后select10号path中的第7号。
但是每个数字只能从10个select中编码select。 其他具有固定基数的系统，如二进制和hex，也只能从固定数量的选项中编码select序列。 我们想要一个可变基数的系统，类似于时间单位，“14:05:29”是24小时14分，60分60分，60分29秒。
如果我们把通用的数字到string和string到数字的函数，并把他们骗到使用混合基数呢？ 而不是像parseInt（'beef'，16）和（48879）.toString（16）那样采用一个单独的基数，他们将每个数字取一个基数。
function pack(digits, radixes) { var n = 0; for (var i = 0; i < digits.length; i++) { n = n * radixes[i] + digits[i]; } return n; } function unpack(n, radixes) { var digits = []; for (var i = radixes.length - 1; i >= 0; i--) { digits.unshift(n % radixes[i]); n = Math.floor(n / radixes[i]); } return digits; }
这是否工作？
// Decimal system pack([4, 2], [10, 10]); // => 42 // Binary system pack([1, 0, 1, 0, 1, 0], [2, 2, 2, 2, 2, 2]); // => 42 // Factorial system pack([1, 3, 0, 0, 0], [5, 4, 3, 2, 1]); // => 42
现在倒退了：
unpack(42, [10, 10]); // => [4, 2] unpack(42, [5, 4, 3, 2, 1]); // => [1, 3, 0, 0, 0]
这真是太美了。 现在让我们将这个参数数字系统应用于排列问题。 我们将考虑A, B, C, D长度2个排列。 他们的总数是多less？ 让我们看看：首先我们画4个项目中的一个，然后是剩下的3个项目之一，即4 * 3 = 12绘制2个项目的方法。 这12种方式可以打包成整数[0..11]。 那么，让我们假装已经打包好了，然后尝试拆包：
for (var i = 0; i < 12; i++) { console.log(unpack(i, [4, 3])); } // [0, 0], [0, 1], [0, 2], // [1, 0], [1, 1], [1, 2], // [2, 0], [2, 1], [2, 2], // [3, 0], [3, 1], [3, 2]
这些数字代表select，而不是原始数组中的索引。 [0，0]并不意味着取A, A ，则表示从A, B, C, D （即A）中取项0，然后从剩下的B, C, D （即B） 。 由此产生的排列是A, B 。
另一个例子：[3,2]意味着从A, B, C, D （这是D），然后从剩余的列表A, B, C （即C）获取项目＃3。 由此产生的排列是D, C 。
这个映射称为Lehmer代码 。 让我们将所有这些Lehmer代码映射到排列：
AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC
这正是我们需要的。 但是，如果你看看unpack函数，你会发现它从右到左产生数字（以反转pack的行为）。 从3的select在4的select之前得到解压。这是不幸的，因为我们希望在从3中select之前从4个元素中进行select。如果不能这样做，我们必须首先计算Lehmer码，将其累加到临时数组中，然后将其应用于项目数组以计算实际排列。
但是如果我们不关心字典顺序，我们可以假装我们想从3个元素中进行select，然后从4中select。然后4的select将首先从unpack出来。 换句话说，我们将使用unpack(n, [3, 4])而不是unpack(n, [4, 3]) 。 这个技巧允许计算Lehmer代码的下一个数字，并立即将其应用到列表中。 这就是nth_permutation()工作原理。
最后我要提的一点是， unpack(i, [4, 3])与阶乘数系统密切相关。 再看看第一棵树，如果我们想要长度为2的排列没有重复，我们可以跳过每一个排列的第二个索引。 这将给我们12个长度为4的排列，可以将其排列成长度为2的排列。
for (var i = 0; i < 12; i++) { var lehmer = unpack(i * 2, [4, 3, 2, 1]); // Factorial number system console.log(lehmer.slice(0, 2)); }
这取决于你“sorting”你的排列方式（例如字典顺序）。
一个办法是做阶乘系统 ，它给你一个[0，n！]和所有排列之间的双射。
那么对于[0，n！]中的任何数字i，您都可以计算第i个排列而不用计算其他排列。
这个阶乘写作是基于这样一个事实：[0和n！]之间的任何数字都可以写成：
SUM( ai.(i!) for i in range [0,n-1]) where ai <i
（这与基本分解非常相似）
有关此分解的更多信息，请参阅此主题： https : //math.stackexchange.com/questions/53262/factorial-decomposition-of-integers
希望能帮助到你
正如这个维基百科文章所述，这种方法相当于计算lehmer代码 ：
生成n置换的一个显而易见的方法是生成Lehmer代码的值（可能使用到n的整数的阶乘数系统表示），并将它们转换成相应的置换。 然而，后面的步骤虽然直截了当，但很难高效地实现，因为它需要n个操作，每个操作在一个任意位置select一个序列并从中删除; 作为数组或链表的明显表示，都需要（由于不同的原因）关于n2 / 4操作来执行转换。 因为n可能相当小（特别是如果需要产生所有排列的话），但这不是一个太大的问题，但是事实certificate，对于随机系统和系统生成来说，都有简单的替代方法，它们的效果会更好。 由于这个原因，尽pipe当然有可能采用一种特殊的数据结构，这种结构在O（n log n）时间内可以执行从莱默码到排列的转换。
所以你可以做的最好的一个n元素是O（n ln（n））与一个适应的数据结构。
这是一个在线性时间内排列和排列之间转换的algorithm。 但是，它使用的排名不是词典。 这很奇怪，但一致。 我要给出两个function，一个从一个等级转换到一个排列，一个做相反的转换。
首先，要排名（从排名到排列）
Initialize: n = length(permutation) r = desired rank p = identity permutation of n elements [0, 1, ..., n] unrank(n, r, p) if n > 0 then swap(p[n-1], p[r mod n]) unrank(n-1, floor(r/n), p) fi end
接下来要排名：
Initialize: p = input permutation q = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n) n = length(p) rank(n, p, q) if n=1 then return 0 fi s = p[n-1] swap(p[n-1], p[q[n-1]]) swap(q[s], q[n-1]) return s + n * rank(n-1, p, q) end
这两者的运行时间是O（n）。
有一个很好的，可读的论文，解释了为什么这样工作：在线性时间sorting和未sorting排列，由Myrvold和Ruskey，信息处理快报第79卷，第6期，2001年9月30日，第281-284页。
这里是一个简短而且速度非常快的（在元素数量上是线性的）解决scheme，用于任何元素列表（下面例子中的13个首字母）：
from math import factorial def nthPerm(n,elems):#with n from 0 if(len(elems) == 1): return elems[0] sizeGroup = factorial(len(elems)-1) q,r = divmod(n,sizeGroup) v = elems[q] elems.remove(v) return v + ", " + ithPerm(r,elems)
例子 ：
letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m'] ithPerm(0,letters[:]) #--> a, b, c, d, e, f, g, h, i, j, k, l, m ithPerm(4,letters[:]) #--> a, b, c, d, e, f, g, h, i, j, m, k, l ithPerm(3587542868,letters[:]) #--> h, f, l, i, c, k, a, e, g, m, d, b, j
注：我给letters[:] （一个letters的副本），而不是字母，因为该function修改其参数元件（删除所选元素）
如果将所有的排列存储在内存中，例如在一个数组中，您应该能够在O（1）次的时间内将它们一次性地取出。
这意味着你必须存储所有的排列，所以如果计算所有的排列需要很长的时间，或者存储它们需要一个非常大的空间，那么这可能不是一个解决scheme。
我的build议无论如何都要尝试，如果太大/太慢，就会回来 – 如果一个天真的人能够完成这项工作，那么寻找一个“聪明”的解决scheme是毫无意义的。
