第N个组合 [英] Nth Combination

问题描述

是否可以直接获得nCr所有组合的有序集合的第N个组合?

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

示例:我有四个要素:[6、4、2、1].一次取三个，所有可能的组合为: [[6，4，2]，[6，4，1]，[6，2，1]，[4，2，1]].

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

有没有一种算法可以给我例如排序结果集中的第三个答案[6，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?

推荐答案

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

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

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

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

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

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.

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

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)

将其使用:

>>> 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屋！