How to Generate Fixed-Length Non-Decreasing Integer Lists (0/1 Steps) in Python Without Nested Loops

Learn scalable ways to generate fixed-length non-decreasing integer sequences in Python without nested loops: itertools.product, iterative DFS, and recursion.

When you need all fixed-length integer lists that start at 0 and evolve so that each next element is either equal to the previous one or exactly one greater, the obvious brute-force approach is to hardcode nested loops. That works for very small sizes, but it collapses the moment you scale, because a length of n implies n − 1 loops. Below is a compact walkthrough of the problem and several practical ways to generate these sequences without nesting yourself into a corner.

Problem setup

The requirement is precise: lists are non-decreasing, each adjacent difference is either 0 or 1, and the first element is a chosen start (commonly 0). For length 5, valid examples look like this:

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

The naive approach that doesn’t scale

This direct implementation builds all lists of length 4 with three explicit loops and a filter. It does work, but it doesn’t generalize well beyond trivial sizes.

import math as mth
def make_index_slices(seed):
    out = []
    for a in [0, 1]:
        for b in [0, 1, 2]:
            for c in [0, 1, 2, 3]:
                if a <= b and b <= c and abs(a - b) < 2 and abs(b - c) < 2:
                    out.append([seed, seed + a, seed + b, seed + c])
    return out
print(make_index_slices(0))

It produces the expected eight sequences of length four, but every extra element would require another loop. That’s the core limitation.

What’s really going on

The structure of the data is simple. Between any two neighboring positions you have exactly two possibilities: keep the same number or increase it by one. That means you can represent the whole list by a series of binary choices for the n − 1 gaps. The idea even maps cleanly to binary numbers because a block of n − 1 bits encodes all such choices.

Solution 1: Cartesian product of deltas

One straight path is to iterate over all 0/1 delta combinations of length n − 1 and accumulate from the starting value. This avoids nested loops altogether and reads directly from the problem statement.

from itertools import product
def build_traces(length, start=0):
    if length == 0:
        return []
    stepspace = product([0, 1], repeat=length - 1)
    all_rows = []
    for step_seq in stepspace:
        row = [start]
        cur = start
        for step in step_seq:
            cur += step
            row.append(cur)
        all_rows.append(row)
    return all_rows
def show_traces(items, cap=10):
    print(f"Total sequences: {len(items)}")
    print("Sample sequences:")
    for idx, s in enumerate(items[:cap]):
        print(s)
    if len(items) > cap:
        print(f"... (showing first {cap} of {len(items)})")
if __name__ == "__main__":
    print("\nSequences starting with 0, length 4:")
    show_traces(build_traces(4, 0))

This version uses a direct 0/1 search space and builds each sequence incrementally from the chosen start.

Solution 2: Iterative depth-first expansion with a stack

If you prefer avoiding itertools while still keeping control over the growth, a stack-based expansion is a compact option. It expands either “stay” or “increment” at each step until the sequence reaches the requested length.

def build_traces_iter(length, start=0):
    if length <= 0:
        return []
    all_rows = []
    todo = [(start, [start], length - 1)]
    while todo:
        last, path, left = todo.pop()
        if left == 0:
            all_rows.append(path)
            continue
        todo.append((last, path + [last], left - 1))
        todo.append((last + 1, path + [last + 1], left - 1))
    return all_rows
def show_traces_iter(items, cap=10):
    print(f"Total sequences: {len(items)}")
    print("Sample sequences:")
    for idx, s in enumerate(items[:cap]):
        print(s)
    if len(items) > cap:
        print(f"... (showing first {cap} of {len(items)})")
if __name__ == "__main__":
    for ln in [4, 5]:
        print(f"\nSequences of length {ln}:")
        payload = build_traces_iter(ln)
        show_traces_iter(payload)
    print("\nSequences starting with 5, length 3:")
    show_traces_iter(build_traces_iter(3, 5))

It is explicit about the state it carries forward and makes it easy to see how the two choices branch at each position.

Solution 3: Recursive construction

A recursive formulation mirrors the definition: take the last value and append either the same value or one greater until the target length is reached.

def build_traces_rec(length, start=0):
    def dive(buf, left):
        if left == 0:
            return [buf]
        prev = buf[-1]
        choices = [prev] if left == 1 else [prev, prev + 1]
        acc = []
        for nxt in choices:
            acc.extend(dive(buf + [nxt], left - 1))
        return acc
    if length == 0:
        return []
    return dive([start], length - 1)
print(build_traces_rec(5))

This version keeps the logic close to the rule set and is easy to reason about step by step.

Why this matters

Moving away from hardcoded nested loops pays off quickly. You get solutions that scale with the sequence length, code that is easier to test and modify, and a direct mapping from problem constraints to implementation. When each adjacent pair has only two options, there is no reason to manually unroll that choice for every position.

Takeaways

Start with the rule that each next value is either equal to or one more than the previous value, and treat the construction as a sequence of binary decisions. Whether you choose a Cartesian product of deltas, a compact stack-based build, or a recursive formulation, each approach sidesteps brittle nesting and keeps the intent readable. Preserve the ability to change the starting value when you need a different base index, and verify results on small lengths to ensure the shape matches expectations before scaling up.