计算字母表的第n 6个字符排列 [英] Computing the nth 6 character permutation of an alphabet

问题描述

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

I have been researching for days trying to figure out a solution to this problem. I would be happy to pay someone for consulting time to solve this if need be.

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

I am currently using Python itertools to generate 6 character permutations of a 32 character alphabet. Via the following command:

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

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

From the documentation, this function produces "r-length tuples, all possible orderings, no repeated elements".

您可以通过以下命令使用该库来抓取一部分结果排列（本示例抓取了前10个排列，即0-10：

You can use the library to grab a slice of the resulting permutations via the following command (this example grabs the first 10 permutations, 0-10:

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

迭代结果gen2时，我得到的正是我想要的：

When iterating over the result gen2, I get exactly what I want:

('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个元素，然后才能将其返回给您。可以想象，这效率很低并且返回时间很长。

This is great, but my real desire is to be able to pick any arbitrary permutation and grab it from the permutation list (without having to store all possible permutation values). If my calculations are correct, when generating 6 character sequences of the alphabet listed above there are 652,458,240 possible combinations. So I would like to be able to do something like grab the 10,353,345th permutation. The problem is that if you use the islice function above to grab this permutation it has to iterate over the entire set of permutations up to 10,353,345th element before returning it to you. As you can imagine, this is very inefficient and takes a long time to return.

我的问题是，实现所需计算的算法是什么？我已经进行了很多关于因子分解和基数n转换的研究，但是找不到任何解释如何实现接近我想要的结果或可以修改算法以实现此结果的东西。

My question is, what is the algorithm to achieve the computation desired? I've done quite a bit of research on factorial decomposition and base n conversions, but have been unable to find anything explaining how to achieve something close to what I want or an algorithm that I can modify to achieve this result.

任何帮助将不胜感激！

推荐答案

你是什么在组合算法中，其外观称为 unrank 。考虑固定集合S的元素列表， unrank_S（i）返回 i -th列表中的元素，而不计算列表。因此，这里的 S 是 Perm（n，k）：所有 k -一组大小为 n 的排列。如您所知，此集合的大小为 n！/ k！。一种方法是使用虚数

What you are looking is called unrank in combinatorial algorithm. Consider the list of the element of a set S in a fixed order, unrank_S(i) returns the i-th element of the list without computing the list. So your S here is Perm(n, k) : the list of all k-permutation of a set of size n. As you know the size of this set is n!/k!. One way to do that is to use Factoradic numbers

这是python中的一个未排序算法：

Here is an unrank algorithm in 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']

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

Of course you might want to compute factorial using a better method or even to cache it in a pre-computed array to avoid recomputing it.

这篇关于计算字母表的第n 6个字符排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！