能否在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个元素（这个例子中是第二个）是abd。是否可以在不创建整个组合列表的情况下得到该值（abd）？

我之所以问这个问题，是因为我的数据有大约1,000,000个字符，而创建完整的m字符长度组合列表以获取第k个元素是不可能的。

解决方案可以是伪代码，或者是链接到描述此问题的页面（不幸的是，我没有找到这样的页面）。

谢谢！

- jack44

---

为此，您需要为组合定义一个明确定义的顺序。 - Björn Pollex

Answer 1

基本上，将索引用阶乘数系统表示，并使用其数字作为原始序列的选择（不重复选择）。

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

- user227667

---

这会不会更有帮助？（指链接中的内容） - Rosh Oxymoron

是的，我是个白痴。我把它看成了排列而不是组合。它们之间可能存在一个简单的映射，例如从N个唯一元素中取k个元素的第j个组合与N个元素的第j(k!)((N-k!)个排列的前k个元素相同。但也可能不是这样。 - user227667

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)

- hugomg

Answer 3

首先计算 r = !n/(!m*!(n-m))，其中 n 是元素的数量。

然后，floor(r/k) 是结果中第一个元素的索引，

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

执行 m--、n-- 和 k = r%k，并重复此过程，直到 m 为 0（提示：当 k 为 0 时，只需将以下字符复制到结果中）。

- ratchet freak

Answer 4

我编写了一个类来处理与二项式系数相关的常见函数，这似乎是您的问题所属的类型。它执行以下任务：

1. 将任意N选K的所有K索引以漂亮的格式输出到文件中。可以用更具描述性的字符串或字母替换K索引。这种方法使解决这种类型的问题变得非常简单。

2. 将K索引转换为排序二项式系数表中条目的正确索引。这种技术比依赖迭代的旧技术快得多。它通过使用帕斯卡三角形固有的数学属性来实现。我的论文谈到了这一点。我相信我是第一个发现并发布这种技术的人，但我可能错了。

3. 将排序二项式系数表中的索引转换为相应的K索引。我认为它也比其他已发布的技术更快。

4. 使用Mark Dominus的方法来计算二项式系数，这样不太可能溢出，并且可以处理更大的数字。

5. 该类是用.NET C#编写的，并提供了一种使用通用列表来管理与问题相关的对象的方法。此类的构造函数接受一个名为InitTable的布尔值，当为true时，将创建一个通用列表来保存要管理的对象。如果此值为false，则不会创建该表。执行上述4种方法不需要创建表格。提供了访问器方法来访问表格。

6. 有一个相关的测试类，展示了如何使用该类及其方法。它已经通过了2个案例的广泛测试，没有已知的错误。

想要了解这个类以及下载代码，请查看表格化二项式系数。

将这个类转换成Java、Python或C++并不困难。

- Bob Bryan