计算字母表中第n个六字符排列

Question

我已经研究了好几天，试图找出解决这个问题的方法。如果需要，我很乐意支付咨询费用来解决这个问题。

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

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

根据文档，该函数生成“长度为r的元组，所有可能的排列，没有重复元素”。

您可以使用该库通过以下命令获取结果排列的一部分（此示例获取第1-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转换进行了相当多的研究，但无法找到任何解释如何实现接近我想要的东西或可以修改以实现此结果的算法的内容。

非常感谢您的任何帮助！

- Jordan

---

@jonrsharpe OP 似乎已经知道这一点了。 - thefourtheye

这显然不是重复的问题。原帖作者知道https://dev59.com/wGct5IYBdhLWcg3wjuAj中提出的解决方案，但由于效率原因，它对他的问题完全不适用。可能需要数年时间才能完成。 - hivert

Answer 1

你要查找的是组合算法中称为unrank的内容。考虑一个集合S的元素列表以固定顺序排列，unrank_S(i)返回列表中第i个元素而无需计算整个列表。因此，在这里，你的S是Perm(n, k)：大小为n的集合中所有k排列的列表。如你所知，该集合的大小为n!/k!。其中一种方法是使用Factoradic numbers。

以下是Python中的unrank算法：

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']

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

- hivert

Answer 2

我没有太多时间给你完整的解决方案，但以下思路可以提供一些思考线索。

您需要找到以每次取6个字符的方式找到第N^th个排列。
让我们先确定第一个字符。然后剩下25个字符。
从其余字符中获得排列的总数为P = ²⁵C₅ * 5!。

因此，用A作为第一个字符，您可以有P个排列。如果P小于N，则A不能在第一位。

现在将B放在第一位，直到B在第一位的排列总数为2*P。

假设你将第K^th个字符放在第一位，那么到第K^th个字符的排列总数为K*P，其中K*P小于N，并且在保留K+1^th字符后，(K+1)*P超过了N。因此，你需要将所需字符串的K+1^th字符放在第一位。

因此，你需要找到剩余25个字符和5个位置的N-K*P个剩余排列。这样，同样的问题就减少了一个字符、一个位置和更少的排列数量。
因此，对所有位置采用类似的方式解决。

- Shashwat Kumar