Skip to content
Advertisement

All tuples of positive integers

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...

Advertisement

Answer

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.

User contributions licensed under: CC BY-SA
7 People found this is helpful
Advertisement