有可能得到O（1）中mcharacterlength组合的第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。没有这个组合子就可以创造价值吗？在

我这么问是因为我有大约1000000个字符的数据，而且不可能创建完整的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!个总组合。我们可以利用这个事实直接跳到我们想要的组合：

^{pr2}$

Answer 3

首先用n计算r = !n/(!m*!(n-m))元素的数量

那么floor（r/k）是结果中第一个元素的索引

移除（将后面的所有内容向左移动）

m--，n--和k=r%k

重复，直到m为0（提示k为0时，只需将以下字符复制到结果中）