All tuples of positive integers

Question

How do I create a generator that will return tuples of all combinations of positive integers, example for generating triplets.

(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

This code uses a similar approach to Paul Hankin's, but it's more general since it will generate tuples of any desired width, not just 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

output

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)

---

The algorithm for compositions was derived from the technique used for counting the number of compositions explained in the Wikipedia article on compositions. This is essentially a variation of the well-known Stars and Bars technique.

Answer 2

You can generate all tuples of positive integers by enumerating them based on their totals (total=3 first, total=4 second, total=5 third, etc.). Note that total=3 is the smallest total possible, since each element is positive, so we start with t=3.

Within each total, this code generates them in lexicographic order.

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)

If you want a more general version that accepts a parameter n describing the length of the tuples, you can enumerate tuples that sum to t using "Stars and Bars". This gives you non-negative tuples, but you can add one to each value to get unique positive tuples.

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)

An easier-to-understand general method enumerates combinations based on their largest value, and by the first column that the value appears in. In this scheme, a result with largest value t and where t appears in the i'th column has arbitrary values less than t in the columns to the left of i, and arbitrary values less than or equal to t in the columns to the right of i.

This method is relatively easy to understand, but the order in which results come out is a bit odd.

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

This is a brute-force method which assumes no ordering requirement.

Warning: Using set via toolz.unique as here to remove duplicates is memory-intensive and expensive. There are better ways.

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)

Note toolz.unique implements this commonly used recipe, so you do not need access to the 3rd party library.