所有正整数元组

Question

如何创建一个生成器,它将返回所有正整数组合的tulples,例如生成三元组.

(1, 1, 1)
(2, 1, 1)
(1, 2, 1)
(1, 1, 2)
(2, 2, 1)
(2, 1, 2)
(2, 2, 2)
(3, 2, 2)
(2, 3, 2)
# and so on...

Answer 1

这段代码使用了与Paul Hankin类似的方法,但它更通用,因为它会产生任何所需宽度的元组,而不仅仅是3.

from itertools import combinations, count

def compositions(num, width):
    m = num - 1
    first, last = (-1,), (m,)
    for t in combinations(range(m), width - 1):
        yield tuple(v - u for u, v in zip(first + t, t + last))

def ordered_compositions(width):
    for n in count(width):
        yield from compositions(n, width)

# test

width = 3
for i, t in enumerate(ordered_compositions(width), 1):
    print(i, t)
    if i > 30:
        break

产量

1 (1, 1, 1)
2 (1, 1, 2)
3 (1, 2, 1)
4 (2, 1, 1)
5 (1, 1, 3)
6 (1, 2, 2)
7 (1, 3, 1)
8 (2, 1, 2)
9 (2, 2, 1)
10 (3, 1, 1)
11 (1, 1, 4)
12 (1, 2, 3)
13 (1, 3, 2)
14 (1, 4, 1)
15 (2, 1, 3)
16 (2, 2, 2)
17 (2, 3, 1)
18 (3, 1, 2)
19 (3, 2, 1)
20 (4, 1, 1)
21 (1, 1, 5)
22 (1, 2, 4)
23 (1, 3, 3)
24 (1, 4, 2)
25 (1, 5, 1)
26 (2, 1, 4)
27 (2, 2, 3)
28 (2, 3, 2)
29 (2, 4, 1)
30 (3, 1, 3)
31 (3, 2, 2)

该算法compositions源于用于计算维基百科关于组合物的文章中解释的组合物数量的技术.这基本上是众所周知的星条和棒技术的变种.