math - 第 N 个组合

Question

有没有直接的方法来获得 nCr 的所有组合的有序集合的第 N 个组合？

示例:我有四个元素:[6, 4, 2, 1]。一次服用三个的所有可能组合是:
[[6, 4, 2], [6, 4, 1], [6, 2, 1], [4, 2, 1]]。

有没有一种算法可以给我，例如有序结果集中的第三个答案 [6, 2, 1] 没有枚举所有以前的答案？

Answer 1

请注意，您可以通过递归生成第一个元素的所有组合，然后生成所有没有的组合来生成序列。在这两种递归情况下，您都可以删除第一个元素以获取 n-1 个元素的所有组合。在 Python 中:

def combination(l, r):
    if r == 0:
        yield []
    elif len(l) == r:
        yield l
    else:
        for c in (combination(l[1:], r-1)):
            yield l[0:1]+c
        for c in (combination(l[1:], r)):
            yield c

任何时候通过这样的选择生成序列时，您都可以通过计算选择生成的元素数量并将计数与 k 进行比较来递归生成第 k 个元素。如果 k 小于计数，则做出该选择。否则，减去计数并重复您当时可以做出的其他可能选择。如果总有 b选项，您可以将其视为在基数 b 中生成一个数字.如果选择的数量不同，该技术仍然有效。在伪代码中(当所有选项始终可用时):

kth(k, choicePoints)
    if choicePoints is empty
        return empty list
    for each choice in head of choicePoints:
        if k < size of choice
            return choice and kth(k, tail of choicePoints)
        else
            k -= size of choice
    signal exception: k is out-of-bounds

这为您提供了一个基于 0 的索引。如果您想要基于 1，请将比较更改为 k <= size of choice .

棘手的部分(以及伪代码中未指定的部分)是选择的大小取决于先前的选择。请注意，伪代码可用于解决比问题更一般的情况。

对于这个特定问题，有两种选择( b = 2)，第一个选择(即包括第一个元素)的大小由 n-1Cr-1 给出。这是一个实现(需要合适的 nCr ):

def kthCombination(k, l, r):
    if r == 0:
        return []
    elif len(l) == r:
        return l
    else:
        i=nCr(len(l)-1, r-1)
        if k < i:
            return l[0:1] + kthCombination(k, l[1:], r-1)
        else:
            return kthCombination(k-i, l[1:], r)

如果您颠倒选择的顺序，您就颠倒了序列的顺序。

def reverseKthCombination(k, l, r):
    if r == 0:
        return []
    elif len(l) == r:
        return l
    else:
        i=nCr(len(l)-1, r)
        if k < i:
            return reverseKthCombination(k, l[1:], r)
        else:
            return l[0:1] + reverseKthCombination(k-i, l[1:], r-1)

投入使用:

>>> l = [6, 4, 2, 1]
>>> [kthCombination(k, [6, 4, 2, 1], 3) for k in range(nCr(len(l), 3)) ]
[[6, 4, 2], [6, 4, 1], [6, 2, 1], [4, 2, 1]]
>>> powOf2s=[2**i for i in range(4,-1,-1)]
>>> [sum(kthCombination(k, powOf2s, 3)) for k in range(nCr(len(powOf2s), 3))]
[28, 26, 25, 22, 21, 19, 14, 13, 11, 7]
>>> [sum(reverseKthCombination(k, powOf2s, 3)) for k in range(nCr(len(powOf2s), 3))]
[7, 11, 13, 14, 19, 21, 22, 25, 26, 28]