生成第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

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

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

尽管如此，你会对开始的东西有更多乐趣。

Answer 2

如果假设在阵列中的所有值都是在碱正编号系统，其中n是阵列的长度位数，第k个组合将在基 - 正表示k的等价物。

如果您想要开始与给定的组合（即，[1,6,5]），并从那里继续进行，简单地读取此起点在基 - 正的数。然后，您可以通过递增来开始迭代连续组合。

编辑：进一步说明：

让我们从数组开始。该数组包含6个值，所以我们正在使用base-6。我们将假设数组中每个元素的索引是元素的base-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（base -6）= [ '2'， '6'， '5']（组合）

更多关于数个碱基，见http://en.wikipedia.org/wiki/Radix和http://en.wikipedia.org/wiki/Base_%28exponentiation%29