生成第k个组合，而无需生成/重复先前的 [英] Generate kth combination without generating/iterating previous

问题描述

给出一组项目，例如：

[1，2，3，4，5，6]

我想重复生成一定长度的所有可能组合。我想从预定的组合开始（这是组合列表中的一种偏移）。

I'd like to generate all possible combinations of a certain length with repetition. The twist is I'd like to start at a predetermined combination (a sort of offset into the list of combinations).

例如，以此开头：

[1，5，6]

第一个（下一个）组合为：

The first (next) combination would be:

[1，6，6]

我已经成功使用 itertools.combinations_with_replacement（）来生成组合，但是此项目要使用的组合会产生太多组合-首先创建所有组合并迭代到正确的点是不可能的。

I've had success using itertools.combinations_with_replacement() to generate the combinations, but the project this is for will require working with a set that generates way too many combinations - creating them all first and iterating to the correct point is not possible.

我发现用于生成第k个组合的示例似乎无效对我来说很好这个答案似乎是另一种可能性，但我似乎无法将其从C移植到Python。

I've found this example for generating kth combination which doesn't seem to be working very well for me. This answer seemed another possibility, but I can't seem to port it from C to Python.

到目前为止，这是我使用第k个组合示例的代码：

Here's my code so far using the kth combination example:

import operator as op
items = [ 1,2,3,4,5,6 ]

# https://stackoverflow.com/a/4941932/1167783
def nCr(n, r):
    r = min(r, n-r)
    if r == 0: 
        return 1
    numer = reduce(op.mul, xrange(n, n-r, -1))
    denom = reduce(op.mul, xrange(1, r+1))
    return numer // denom

# https://stackoverflow.com/a/1776884/1167783
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)

# get 1st combination of 3 values from list 'items' 
print kthCombination(1, items, 3)

# returns [ 1, 2, 4 ]

任何帮助都会很棒！

推荐答案

您可以映射数字而不是发明轮转时间数字37,289,423,987,239,489,826,364,653（仅计算人类）。 itertools 将返回第一个组合 [1,1,1] ，但是您要 [1 ，5,6] 。只需将[0,4,5] mod 6添加到每个位置。当然，您也可以在数字，对象和模之间来回映射。

Instead of inventing the wheel time number 37,289,423,987,239,489,826,364,653 (that's counting only human beings), you can map the numbers. itertools will return first combination [1,1,1], but you want [1,5,6]. Simply add [0,4,5] mod 6 to each position. You can also map back and forth between numbers, objects, and modulo, of course.

即使每个位置的元素数量不同，此方法也可以使用。

This works even if the number of elements in each position is different.

不过，您将从开始的过程中获得更多乐趣。

You will have more fun with what you started, though.

这篇关于生成第k个组合，而无需生成/重复先前的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！