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.