pythonlistenumeration

Enumerating all possible lists (of any length) of non-negative integers

I would like to generate/enumerate all possible lists of non-negative integers such that the algorithm will generate lists like the following at some point

[1]
[24542,0]
[245,904609,848,24128,350,999]

In other words, for all possible non-negative integers, generate all possible lists which contain that many non-negative integers.

I have figured that the trick for a list with two numbers is to enumerate their values diagonally like this

first value\second value 0 1 2 3
0 0 (this will be generated first) 2 (this third etc.) 5 9
1 1 (this second) 4 8
2 3 7
3 6 
def genpair():
    x = 0
    y = 0
    yield x,y
    maxx = 0
    while True:
        maxx += 1
        x = maxx
        y = 0
        while x >= 0:
            yield x,y
            x -= 1
            y += 1
    
gen = genpair()

for i in range(10):
    print(next(gen))

But does the same trick (or another) also make this work for lists of arbitrary length?

Solution

  • One of infinitely many ways to do this:

    Imagine a number line with cells 1, 2, 3, and up to infinity. Now think of a binary number representation, with bits indicating if there is a "break" at the cell border. So,

    1  -> [1]
10 -> [2]
11 -> [1,1]
100 -> [3]
101 -> [2, 1]
110 -> [1, 2]

    Note how number of bits is the same as the sum of the list, and number of positive bits indicates the number of list elements. Code would look somewhat like:

    def list_gen(n):
    res = []
    counter = 0
    while n:
        counter += 1
        n, flag = divmod(n, 2)
        if flag:
            res.append(counter)
            counter = 0
    return res