java是否可以在O（1）中获得McCharacterLength组合的第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）

我这样问是因为我有大约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!个总组合。我们可以利用这一事实直接跳到我们想要的组合：

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)

Answer 3

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

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

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

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

4. 使用Mark Dominus方法计算二项式系数，该系数溢出的可能性小得多，适用于较大的数字

5. 这门课是用英语写的。NET C#提供了一种通过使用通用列表管理与问题相关的对象（如果有）的方法。这个类的构造函数接受一个名为InitTable的bool值，如果为true，它将创建一个通用列表来保存要管理的对象。如果此值为false，则不会创建表。执行上述4种方法不需要创建表。提供了访问器方法来访问表

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

要阅读这个类并下载代码，请参阅Tablizing The Binomial Coeffieicent

<> P>不应该很难将这个类转换成java、python或C++。p>

Answer 4

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

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

拆下它（将后面的所有内容向左移动）

dom--，n--，k=r%k

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