在 Python 中手动生成 r 组合

Question

我正在尝试手动生成 r 组合（我手动生成这些而不使用 itertools 对我来说绝对必要）。

这是我当前的代码块：

def rcombs(items, r):
    n = len(items)
    s = []
    permuted_items = []
    for i in xrange(0, r):
        s.append(i)

    for i in xrange(1, C(n,r)):
        m = r - 1
        max_val = n - 1
        while (s[m] == max_val):
            m = m - 1
            max_val = max_val - 1

        s[m] = s[m] + 1

        for j in xrange(m + 1, r):
            s[j] = s[j-1] + 1

        temp_ = []
        for k in s:
            temp_.append(items[k])

        permuted_items.append(temp_)

    return permuted_items

def C(n, r):
    return math.factorial(n) / (math.factorial(r) * math.factorial(n - r))

不过，好像漏掉了一些组合。一个简单的例子是寻找 1-组合和 2-组合；算法 returns:

    items = [0, 1, 2, 3, 4]

    1 -combinations:
    [[1], [2], [3], [4]]

    2 -combinations:
    [[0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

对于 1 种组合，缺少 [0]，对于 2 种组合，缺少 [0,1]。

感谢所有帮助。

Answer 1

你只是忘记输出第一个结果 s 从 0 到 r - 1.

...
permuted_items.append([items[k] for k in s])
for i in xrange(1, C(n,r)):
... # rest

在 Python 中手动生成 r 组合

Manual generation of r-combinations in Python

python

combinatorics