是否有可能在O(1)中获得m字符长度组合的第k个元素？

Question

你知道如何在O(1)中获得m元素组合的第k个元素吗？预期的解决方案应适用于任何大小的输入数据和任何m值.

让我通过示例(python代码)解释这个问题:

>>> import itertools
>>> data = ['a', 'b', 'c', 'd']
>>> k = 2
>>> m = 3
>>> result = [''.join(el) for el in itertools.combinations(data, m)]
>>> print result
['abc', 'abd', 'acd', 'bcd']
>>> print result[k-1]
abd

对于给定数据,m元素组合的第k个(在该示例中为第2个)元素是abd.是否可以在不创建整个组合列表的情况下获得该值(abd)？

我问,因为我有大约1,000,000个字符的数据,并且不可能创建完整的m字符长度组合列表来获得第k个元素.

解决方案可以是伪代码,也可以是描述此问题的页面的链接(遗憾的是,我没有找到).

谢谢!

Answer 1

http://en.wikipedia.org/wiki/Permutation#Numbering_permutations

基本上,在阶乘数系统中表达索引,并使用其数字作为原始序列的选择(无替换).

Answer 2

不一定是 O(1)，但以下应该非常快：

采用原始组合算法：

def combinations(elems, m):
    #The k-th element depends on what order you use for
    #the combinations. Assuming it looks something like this...
    if m == 0:
        return [[]]
    else:
        combs = []
        for e in elems:
            combs += combinations(remove(e,elems), m-1)

对于n初始元素和m组合长度，我们有n!/(n-m)!m!总组合。我们可以利用这个事实直接跳到我们想要的组合：

def kth_comb(elems, m, k):
    #High level pseudo code
    #Untested and probably full of errors
    if m == 0:
        return []
    else:
        combs_per_set = ncombs(len(elems) - 1, m-1)
        i = k / combs_per_set
        k = k % combs_per_set
        x = elems[i]
        return x + kth_comb(remove(x,elems), m-1, k)