2

给定一组项目,例如:

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

我想通过重复生成一定长度的所有可能组合。扭曲是我想从预先确定的组合开始(组合列表中的一种偏移量)。

例如,从这个开始:

[ 1, 5, 6 ]

第一个(下一个)组合是:

[ 1, 6, 6 ]

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

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

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

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 ]

任何帮助都会很棒!

4

2 回答 2

3

如果您假设数组中的所有值都是以 n 为基数的编号系统中的数字,其中 n 是数组的长度,则第 k 个组合将等效于以 n 为基数表示的 k。

如果您想从给定的组合(即 [1,6,5])开始并从那里继续,只需将此起点读取为 base-n 中的数字。然后,您可以通过递增开始迭代连续组合。

编辑:进一步解释:

让我们从数组开始。该数组包含 6 个值,因此我们使用 base-6。我们将假设数组中每个元素的索引是元素的 base-6 值。

base-6 的值范围从 0 到 5。这可能会让人感到困惑,因为我们的示例使用数字,但我们可以使用任何组合来做到这一点。我将在我们组合的数字周围加上“引号”。

给定一个组合 ['1', '6', '5'],我们首先需要将其转换为 base-6 值。'1' 变为 0,'6' 变为 5,'5' 变为 4。使用它们在起始值中的位置作为它们在 base-6 中的幂,我们得到:

(0 * 6^0) + (5 * 6^1) + (4 * 6^2) = 174(十进制)

如果我们想知道下一个组合,我们可以加 1。如果我们想知道前面的 20 个组合,我们加 20。我们也可以减去向后。让我们将 1 添加到 174 并将其转换回 base-6:

175 (十进制) = (1 + 6^0) + (5 * 6^1) + (4 * 6^2) = 451 (base-6) = ['2', '6', '5'] (组合)

有关数字基础的更多信息,请参阅http://en.wikipedia.org/wiki/Radixhttp://en.wikipedia.org/wiki/Base_%28exponentiation%29

于 2013-08-30T01:47:36.940 回答
2

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

即使每个位置的元素数量不同,这也有效。

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

于 2013-08-30T01:49:50.660 回答