从索引生成一个排列

Question

是否有一种有效的算法可以从提供的一个索引生成排列？排列不需要有任何特定的排序，只需要每个可能的索引返回一次每个排列即可。我想要置换的集合都是0~255之间的整数。

Answer 1

如果我正确理解这个问题，问题如下：给你两个整数n和k，你想找到n整数的第k个排列。你不在乎它是第k个词典排列，但它更容易成为词典排列，所以让我们坚持下去。

这还不算太糟。基置换为1,2,3,4...n。这就是k=0的情况。考虑一下如果你交换1和2会发生什么：通过移动1，你传递了1首先到达的每个排列，其中有(n-1)!(因为如果你固定了1，你可以排列2,3,4..n(。因此，算法如下：

for i from 1 to n:
j = k / (n-i)! // integer division, so rounded down
k -= j * (n-i)!
place down the jth unplaced number

这将迭代地产生第k个字典排列，因为它重复地用一组较小的数字来解决子问题，并在此过程中递减k。

Answer 2

python中的模块more-itertools中有一个实现：nth_permutation。

以下是一个实现，改编自more_itertools.nth_permutation:的代码

from sympy import factorial
def nth_permutation(iterable, index):
pool = list(iterable)
n = len(pool)
c = factorial(n)
index = index % c
result = [0] * n
q = index
for d in range(1, n + 1):
q, i = divmod(q, d)
if 0 <= n - d < n:
result[n - d] = i
if q == 0:
break
return tuple(map(pool.pop, result))
print( nth_permutation(range(6), 360) )
# (3, 0, 1, 2, 4, 5)