不使用 itertools 生成重复组合

Question

我对计算机科学和算法理论的经验很少。我需要生成并打印所有组合，并按字典顺序打印大小为 k 的数字 1..n 的重复组合。我应该在不使用 itertools 的情况下完成它。我写了简单的代码来创建所有组合，但这还不足以解决这个任务。

 
n, k = map(int, input().split())
    def gen (n, k, prefix):
        if len(prefix) == n:
            print(*prefix)
            return
       for c in range(1, n + 1):
            if c not in prefix:
                gen(n, k, prefix +[c])
    n1 = gen(n, k, [])

示例输入

3 3

示例输出

请帮我找到解决办法！

Answer 1

递归实现：

def combrep(n, k, pos=0, start = 0, l = []):
    if pos == k:
        print(l)
    else:
        for i in range(start, n):
            combrep(n, k, pos+1, i, l + [i+1])

combrep(3,3)

[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 2, 3]
[1, 3, 3]
[2, 2, 2]
[2, 2, 3]
[2, 3, 3]
[3, 3, 3]

Answer 2

在 documentation 中，它说 itertools.combinations_with_replacement 大致翻译成这个（小的编辑所以它需要一个整数）：

def combinations_with_replacement(n, r):
    pool = tuple(range(n))
    if not n and r:
        return
    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

for i in combinations_with_replacement(3, 3):
    print(i)

for i in combinations_with_replacement(3, 3):
    print(i)

(1, 1, 1)
(1, 1, 2)
(1, 1, 3)
(1, 2, 2)
(1, 2, 3)
(1, 3, 3)
(2, 2, 2)
(2, 2, 3)
(2, 3, 3)
(3, 3, 3)

我无法想象更简单的实现。为什么不从那里开始呢？

不使用 itertools 生成重复组合

Generate combinations with repetition without using itertools

python

algorithm

combinations

combinatorics