python - 计算字母表的第 n 个 6 字符排列

Question

我已经研究了好几天，试图找到解决这个问题的方法。如果需要，我很乐意花钱请人咨询时间来解决这个问题。

我目前正在使用 Python itertools 生成 32 个字符字母表的 6 个字符排列。通过以下命令:

gen = itertools.permutations('ABCDEFGHJKLMNPQRSTUVWXYZ23456789',6) 

根据文档，此函数生成“r 长度的元组，所有可能的顺序，没有重复的元素”。

您可以使用该库通过以下命令获取生成的排列的一部分(此示例获取前 10 个排列，0-10:

gen2 = itertools.islice(gen,0,10)

当迭代结果 gen2 时，我得到了我想要的:

('A', 'B', 'C', 'D', 'E', 'F')
('A', 'B', 'C', 'D', 'E', 'G')
('A', 'B', 'C', 'D', 'E', 'H')
('A', 'B', 'C', 'D', 'E', 'J')
('A', 'B', 'C', 'D', 'E', 'K')
('A', 'B', 'C', 'D', 'E', 'L')
('A', 'B', 'C', 'D', 'E', 'M')
('A', 'B', 'C', 'D', 'E', 'N')
('A', 'B', 'C', 'D', 'E', 'P')
('A', 'B', 'C', 'D', 'E', 'Q')

这很好，但我真正的愿望是能够选择任意排列并从排列列表中获取它(无需存储所有可能的排列值)。如果我的计算是正确的，当生成上面列出的字母表的 6 个字符序列时，有 652,458,240 种可能的组合。所以我希望能够做一些事情，比如捕获第 10,353,345 个排列。问题是，如果您使用上面的 islice 函数来获取此排列，它必须迭代整个排列集直到第 10,353,345 个元素，然后再返回给您。可以想象，这是非常低效的，需要很长时间才能返回。

我的问题是，实现所需计算的算法是什么？我对阶乘分解和以 n 为底的转换做了很多研究，但找不到任何解释如何实现接近我想要的东西的东西，也找不到我可以修改以实现此结果的算法。

如有任何帮助，我们将不胜感激!

Answer 1

你正在寻找的是组合算法中的unrank。考虑以固定顺序排列的集合 S 的元素列表，unrank_S(i) 返回列表的第 i 元素而不计算列表。所以这里的 S 是 Perm(n, k) :所有 k 的列表 - 一组大小 n< 的排列。如您所知，此集合的大小为 n!/k!。一种方法是使用 Factoradic numbers

这是 python 中的一个非排序算法:

def factorial(n):
    if n == 0: return 1
    return n*factorial(n-1)

def unrank(S, k, i):
    S = list(S)   # make a copy to avoid destroying the list
    n = len(S)
    nb = factorial(n) // factorial(n-k)
    if i >= nb:
        raise IndexError
    res = []
    while k > 0:
        nb = nb // n
        pos = i // nb   # the factoradic digits
        i = i % nb      # the remaining digits
        res.append(S[pos])
        del S[pos]
        k = k-1
        n = n-1
    return res

然后

[unrank(range(5), 2, i) for i in range(20)]
 [[0, 1], [0, 2], [0, 3], [0, 4], [1, 0], [1, 2], [1, 3], [1, 4], [2, 0], [2, 1], [2, 3], [2, 4], [3, 0], [3, 1], [3, 2], [3, 4], [4, 0], [4, 1], [4, 2], [4, 3]]

和

unrank(list('ABCDEFGHJKLMNPQRSTUVWXYZ23456789'),6, 128347238)\
['G', 'L', 'E', 'H', 'T', 'R']

当然，您可能希望使用更好的方法计算阶乘，甚至将其缓存在预先计算的数组中以避免重新计算。