从大量符号中获得第N个组合而不重复的最快方法

Question

64个符号有64个！排列。如何从其索引/排名中获得其中一个排列，以及如何在Java、Python或C#中以最快的方式获得这些排列之一的索引/排名
这些排列没有重复，每个排列的长度等于给定给函数的符号数。

Answer 1

第N个排列

iea是，无论你为第一个位置选择哪个数字，剩下的都是(n-1(个元素的排列，所以选择到第一个位置的数字是floor(idx / (n-1)!)。递归地应用这个，你就得到了你想要的排列。

from functools import lru_cache
@lru_cache
def factorial(n):
if n <= 1: return 1
else: return n * factorial(n-1);
def nth_permutation(idx, length, alphabet=None, prefix=()):
if alphabet is None:
alphabet = [i for i in range(length)]
if length == 0:
return prefix
else:
branch_count = factorial(length-1)
for d in alphabet:
if d not in prefix:
if branch_count <= idx:
idx -= branch_count;
else:
return nth_permutation(idx, 
length-1, alphabet, prefix + (d,))

这将返回一个表示所请求排列的元组，如果您愿意，您可以传递一个自定义字母表。

示例

nth_permutation(1, 10)
# (0, 1, 2, 3, 4, 5, 6, 7, 9, 8)
nth_permutation(1000, 10)
# (0, 1, 2, 4, 6, 5, 8, 9, 3, 7)
1000
nth_permutation(3628799, 10)
# (9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
nth_permutation(10**89, 64)
# [[50 27 40 11 60 12 10 49]
# [63 29 41  0  2 48 43 47]
# [57  6 59 56 17 58 52 39]
# [13 51 25 23 45 24 26  7]
# [46 20 36 62 14 55 31  3]
# [ 4  5 53 15  8 28 16 21]
# [32 30 35 18 19 37 61 44]
# [38 42 54  9 33 34  1 22]]

排列指数

给定排列的索引是第一元素的index乘以(n-1)!加上剩余项的排列的秩。

def permutation_index(item, alphabet=None):
if alphabet is None:
alphabet = sorted(item)
n = len(item)
r = 0
for i, v in enumerate(item):
# for every (item[j] > item[i]) we have to increase (n - i)!
# the factorials are computed recursively
# grouped in r
r = sum(1 for u in item[i+1:] 
if alphabet.index(u) < alphabet.index(v)) + r * (n - i)
return r;

一致性检查

permutation_index(nth_permutation(1234567890, 16))