How to generate all non-decreasing sequences with a maximum step of 1?

Question

I am trying to get a list of every possible combination of the numbers 0-14 with certain constraints. I'm not exactly sure how to word this so let me explain.

• Each list will have a length of 15.
• The first list will be [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
• The value at each index in each list cannot exceed the index itself, and can be either the same as the previous number, or one higher than the previous number.
• The final list will be [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14].

I am looking to get a list of lists that contains all possible sequences with these constraints (e.g. one possible sequence would be [0, 1, 1, 2, 2, 3, 4, 5, 6, 6, 7, 7, 7, 8, 8] ).

How do I go about doing this?

Answer 1

Not as elegant (or well performing) as @kaya3's answer but this is a more intuitive approach for me. The basic idea is to recurse on the a list that has a certain starting integer and the remaining length.

def next(i, n):
    if n <= 1:
        return [[i]]
    else:
        without_increment = list(next(i, n-1))
        with_increment = list(next(i+1, n-1))
        return map(lambda l: [i] + l, without_increment + with_increment)

n = 3
list(next(0, n))

Output

[[0, 0, 0], [0, 0, 1], [0, 1, 1], [0, 1, 2]]

Answer 2

Since the first list element is always 0, we have two choices for each remaining element; should it equal the previous element, or be one higher? That gives 2^14 different combinations.

To generate them, we can take the product of 14 copies of (0, 1), and convert each to their sequence of partial sums using itertools.accumulate:

import itertools

def solution(n):
    for p in itertools.product((0, 1), repeat=n):
        yield (0,) + tuple(itertools.accumulate(p))

Example:

>>> for p in solution(3):
...     print(p)
... 
(0, 0, 0, 0)
(0, 0, 0, 1)
(0, 0, 1, 1)
(0, 0, 1, 2)
(0, 1, 1, 1)
(0, 1, 1, 2)
(0, 1, 2, 2)
(0, 1, 2, 3)