所有正整数元组

Question

我如何创建一个生成器，它将 return 所有正整数组合的元组，例如生成三元组。

(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

这是一种假设没有顺序要求的蛮力方法。

警告：通过toolz.unique 使用set 来删除重复项会占用大量内存且成本高昂。还有更好的方法。

from itertools import count, product, chain
from toolz import unique

def gen_tups(n):
    yield from unique(chain.from_iterable(product(range(1, c), repeat=n) \
                      for c in count(start=2))):

x = gen_tups(3)

next(x)  # (1, 1, 1)
next(x)  # (1, 1, 2)
next(x)  # (1, 2, 1)

注意 toolz.unique 实现了这个 commonly used recipe，因此您不需要访问第 3 方库。

Answer 2

您可以通过根据总数（第一个总数=3，第二个总数=4，第三个总数=5，等等）枚举它们来生成所有正整数元组。请注意，total=3 是可能的最小总数，因为每个元素都是正数，所以我们从 t=3.

开始

在每个总数中，此代码按字典顺序生成它们。

def posint():
    t = 3
    while True:
        for i in range(1, t-1):
            for j in range(1, t-i):
                    yield i, j, t-i-j
        t += 1

for i, j, k in posint():
    print(i, j, k)

如果您想要一个更通用的版本，它接受描述元组长度的参数 n，您可以使用 "Stars and Bars" 枚举总和为 t 的元组。这为您提供了非负元组，但您可以将每个值加一以获得唯一的正元组。

import itertools

def posint(n):
    for t in itertools.count(0):
        for c in itertools.combinations(range(t + n - 1), n - 1):
            yield [c[0]+1] + [c[i]-c[i-1] for i in range(1, len(c))] + [t+n-1-c[-1]]

for c in posint(5):
    print(c)

一种更容易理解的通用方法是根据组合的最大值，以及该值出现的第一列来枚举组合。在这种方案中，具有最大值t的结果以及t出现在i'中的位置第 i 列在 i 左侧的列中具有小于 t 的任意值，在 i 右侧的列中具有小于或等于 t 的任意值。

这个方法比较容易理解，但是结果出来的顺序有点奇怪

import itertools

def posint(n):
    for t in itertools.count(1):
        for i in range(n):
            for c1 in itertools.product(range(1, t), repeat=i):
                for c2 in itertools.product(range(1, t+1), repeat=n-i-1):
                    yield c1 + (t,) + c2

for c in posint(3):
    print(c)

Answer 3

此代码使用与 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 的算法源自维基百科关于 compositions. This is essentially a variation of the well-known Stars and Bars 技术的文章中用于计算作品数量的技术。

所有正整数元组

All tuples of positive integers

python

combinatorics