Create an infinite nested list of list

Question

I have a task to make an list of list following specific rules. List must represent a tree with a root and branches from this root with specific color. Each branch should be represented as a list of its child elements (one black branch generates 3 white; 1 white branch generates 2 black). For example: root=['black'], first branches [['white','white','white']], next iteration should be [[[black,black],[black,black],[black,black]]] and so on.

This infinite list should be stored in global variable. Is it possible? My code, which generates such list do it only for for a predetermined number of steps.

root = ['b']
def change(root):
    for index, item in enumerate(root):
        if isinstance(item, list):
            change(item)
        elif item == 'b':
            root[index] = ['w','w','w']
        elif item == 'w':
            root[index] = ['b','b']
    return root

for i in range(3):
    tree=change(root)
print(tree)

How can I generate infinite list if it is possible?

You can't produce an actual infinite list; there is never going to be enough memory, as that's a finite resource.. — Martijn Pieters, Jan 16 '17 at 19:25
Other than memory, there is no limit to how many levels deep you can nest lists, however. — Martijn Pieters, Jan 16 '17 at 19:25
@MartijnPieters Perhaps he means he needs to write a program that *yields* a potentially-infinite list of lists that follows a certain pattern. — Tagc, Jan 16 '17 at 19:27
@MartijnPieters There is a maximum recursive call limit. Won't that be applicable here? since OP makes recursive call. Hence, memory is not the only constraint — Moinuddin Quadri, Jan 16 '17 at 19:29
@MoinuddinQuadri: I had barely looked at the code, to be honest. Yes, the code, as written, would be subject to recursion limits. It could be converted to use loops instead. — Martijn Pieters, Jan 16 '17 at 19:30
@Tagc: perhaps, but the question asks: *How can I generate infinite list if it is possible*. — Martijn Pieters, Jan 16 '17 at 19:31
@Martijn Pieters: I apologize for the poor formulation of the question. I means what Tagc said. You say, it could be converted to use loop instead to avoid the recursion limits. How can I do it? — Евгений М, Jan 16 '17 at 19:46
@ЕвгенийМ: keep a reference to the innermost list object containing non-nested lists. Update that each loop iteration, replacing the contents with a new list, update the reference to the new list, continue to the next iteration. — Martijn Pieters, Jan 16 '17 at 20:05

score 1 · Accepted Answer · answered Jan 16 '17 at 21:03

1

If I'm understanding your requirements correctly, this creates the entire infinite tree in memory (but requiring only finite memory because it refers to itself):

black = []
white = [black, black]
black.append([white, white, white])

root = black    # or white, if you prefer

Note that the 'b' and 'w' leaf nodes never appear in the tree, as you can never actually reach them.

answered Jan 16 '17 at 21:03

jasonharper

9,450
2
18
42

Ah, I get what OP was after now. Although I'm not sure what utility he gets out of it (every element and every child of every element would just be represented as `[[[[...]], [[...]]], [[[...]], [[...]]], [[[...]], [[...]]]]`). +1 for understanding the requirements better than me though. – Tagc Jan 16 '17 at 22:23

score 0 · Answer 2 · edited May 23 '17 at 12:01

In the comments on your question, I suggested:

@MartijnPieters Perhaps he [OP] means he needs to write a program that yields a potentially-infinite list of lists that follows a certain pattern.

You replied that that's what you want, so I had a go at it - the code I post involves using a function generator, which you can use to generate a potentially never-ending sequence that follows the pattern you specify (if we were to assume infinite memory).

A short while ago I saw an incredible solution posted by someone to generate the sequence of coprime pairs. It was the first time I'd been made aware of the whole mind-blowing concept of "self-recursive generators". You can use them to do some pretty awesome things, like generate the Kolakoski sequence.

In any case, I had a gut feeling that I could use self-recursive generators to solve your problem. The goods news is that my code works. The bad news is that I have no idea why my code works. Here it is:

from enum import Enum


class Colour(Enum):
    BLACK = 'black'
    WHITE = 'white'

def generate_tree(curr_colour = Colour.BLACK):
    yield [curr_colour]
    for sub_tree in generate_tree(Colour.WHITE if curr_colour == Colour.BLACK else Colour.BLACK):
        if curr_colour == Colour.WHITE:
            tree = [sub_tree, sub_tree]
        else:
            tree = [sub_tree, sub_tree, sub_tree]

        yield tree

if __name__ == '__main__':
    generator = generate_tree()
    for _ in range(3):
        print(next(generator))

Output for n=3

[<Colour.BLACK: 'black'>]
[[<Colour.WHITE: 'white'>], [<Colour.WHITE: 'white'>], [<Colour.WHITE: 'white'>]]
[[[<Colour.BLACK: 'black'>], [<Colour.BLACK: 'black'>]], [[<Colour.BLACK: 'black'>], [<Colour.BLACK: 'black'>]], [[<Colour.BLACK: 'black'>], [<Colour.BLACK: 'black'>]]]

You can use the variant below to have a program that keeps generating the tree indefinitely, waiting at each iteration for user input:

if __name__ == '__main__':
    generator = generate_tree()
    while True:
        print(next(generator))
        input()

Create an infinite nested list of list

2 Answers2