生成第k个组合而不生成/迭代上一个

Question

给定一组项目，例如：

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

我想用重复来生成所有可能的长度组合。关键是我想从一个预先确定的组合开始（一种组合列表中的偏移量）。在

例如，从这个开始：

[ 1, 5, 6 ]

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

[ 1, 6, 6 ]

我已经成功地使用itertools.combinations_with_replacement()来生成组合，但是这个项目需要使用一个生成太多组合的集合——首先创建它们并迭代到正确的点是不可能的。在

我发现this example for generating kth combination对我来说效果不太好。This answer似乎是另一种可能，但我似乎无法将其从C移植到Python。在

以下是我目前为止使用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 ]

任何帮助都是伟大的！在

Answer 1

不用发明车轮时间编号37289423987239489826364653（只计算人类），你可以映射这些数字。itertools将返回第一个组合[1,1,1]，但您需要{}。只需将[0,4,5]mod 6添加到每个位置。当然，您还可以在数字、对象和模之间来回映射。在

即使每个位置的元素数量不同，也可以这样做。在

不过，你会从你开始的事情中获得更多乐趣。在

Answer 2

如果假设数组中的所有值都是base-n编号系统中的数字，其中n是数组的长度，那么第k个组合将相当于以base-n表示的k

如果你想从一个给定的组合（即[1,6,5]）开始并从那里继续，只需将这个起始点读作以n为基数的数字。然后你可以通过递增的方式开始迭代连续的组合。在

编辑：进一步说明：

让我们从数组开始。数组包含6个值，因此我们使用的是以6为底的值。我们假设数组中每个元素的索引都是元素的6进制值。在

以6为基数的值的范围为0到5。这可能会让人困惑，因为我们的示例使用数字，但我们可以使用任何组合。我会在我们合并的数字周围加上引号。在

给定一个组合['1'，'6'，'5']，我们首先需要将其转换为以6为底的值“1”变为0，“6”变为5，“5”变为4。利用它们在起始值中的位置作为它们在基数6中的幂，我们得到：

（0*6^0）+（5*6^1）+（4*6^2）=174（十进制）

如果我们想知道下一个组合，我们可以加1。如果我们想知道前面的20个组合，我们加上20个。我们也可以用减法来倒退。让我们把1加到174，然后再把它转换回以6为底：

175（十进制）=（1+6^0）+（5*6^1）+（4*6^2）=451（以6为底）=['2'，'6'，'5']（组合）

有关基数的更多信息，请参见http://en.wikipedia.org/wiki/Radix和http://en.wikipedia.org/wiki/Base_%28exponentiation%29