第 N 个组合 [英] Nth Combination

问题描述

有没有直接的方法可以得到 nCr 的所有组合的有序集合的第 N 个组合?

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

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

解决方案

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

def 组合(l, r):如果 r == 0:屈服 []elif len(l) == r:产量 l别的:对于 c in (combination(l[1:], r-1)):产量 l[0:1]+c对于 c in (combination(l[1:], r)):产量 c

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

kth(k, choicePoints)如果选择点为空返回空列表对于选择头中的每个选择点:如果 k＜选择的大小返回选择和 kth(k, 选择点的尾部)别的k -= 选择的大小信号异常:k 越界

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

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

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

def kthCombination(k, l, r):如果 r == 0:返回 []elif len(l) == r:返回 l别的:i=nCr(len(l)-1, r-1)如果 k＜一世:返回 l[0:1] + kthCombination(k, l[1:], r-1)别的:返回 kthCombination(k-i, l[1:], r)

如果你颠倒了选择的顺序，你就颠倒了顺序.

def reverseKthCombination(k, l, r):如果 r == 0:返回 []elif len(l) == r:返回 l别的:i=nCr(len(l)-1, r)如果 k＜一世:返回 reverseKthCombination(k, l[1:], r)别的:返回 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]

Is there a direct way of getting the Nth combination of an ordered set of all combinations of nCr?

Example: I have four elements: [6, 4, 2, 1]. All the possible combinations by taking three at a time would be: [[6, 4, 2], [6, 4, 1], [6, 2, 1], [4, 2, 1]].

Is there an algorithm that would give me e.g. the 3rd answer, [6, 2, 1], in the ordered result set, without enumerating all the previous answers?

解决方案

Note you can generate the sequence by recursively generating all combinations with the first element, then all combinations without. In both recursive cases, you drop the first element to get all combinations from n-1 elements. In 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

Any time you're generating a sequence by making a choice like this, you can recursively generate the k_th element by counting how many elements a choice generates and comparing the count to k. If k is less than the count, you make that choice. Otherwise, subtract the count and repeat for the other possible choices you could make at that point. If there are always b choices, you can view this as generating a number in base b. The technique still works if the number of choices varies. In pseudocode (when all choices are always available):

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

This gives you a 0-based index. If you want 1-based, change the comparison to k <= size of choice.

The tricky part (and what is unspecified in the pseudocode) is that the size of a choice depends on previous choices. Note the pseudocode can be used to solve a more general case than the problem.

For this specific problem, there are two choices (b= 2) and the size of the 1st choice (i.e. including the 1^st element) is given by _n-1C_r-1. Here's one implementation (which requires a suitable 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)

If you reverse the order of the choices, you reverse the order of the sequence.

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)

Putting it to use:

>>> 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]

这篇关于第 N 个组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！