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 valuesecond 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?
6
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
1
With a recursive helper and an ever-increasing budget, where each number costs itself+1:
def genlists():
def gen(budget):
if not budget:
yield []
for x in range(budget):
for y in gen(budget-(x+1)):
yield [x] + y
budget = 0
while True:
yield from gen(budget)
budget += 1
Demo:
for lst in genlists():
print(lst)
Output (Attempt This Online!):
[]
[0]
[0, 0]
[1]
[0, 0, 0]
[0, 1]
[1, 0]
[2]
[0, 0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 2]
[1, 0, 0]
[1, 1]
[2, 0]
[3]
[0, 0, 0, 0, 0]
[0, 0, 0, 1]
...