J'ai pour tâche de faire une liste de liste suivant des règles spécifiques. La liste doit représenter un arbre avec une racine et des branches de cette racine avec une couleur spécifique. Chaque branche doit être représentée comme une liste de ses éléments enfants (une branche noire génère 3 blancs; 1 branche blanche génère 2 noirs). Par exemple: root=['black'], premières branches [['white','white','white']], la prochaine itération devrait être [[[black,black],[black,black],[black,black]]] et ainsi de suite.

Cette liste infinie doit être stockée dans une variable globale. C'est possible? Mon code, qui génère une telle liste, ne le fait que pour un nombre d'étapes prédéterminé.

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)

Comment puis-je générer une liste infinie si c'est possible?

-2
Евгений М 16 janv. 2017 à 22:24

2 réponses

Meilleure réponse

Si je comprends bien vos besoins, cela crée tout l'arbre infini en mémoire (mais ne nécessitant qu'une mémoire finie car il se réfère à lui-même):

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

root = black    # or white, if you prefer

Notez que les nœuds feuilles 'b' et 'w' n'apparaissent jamais dans l'arborescence, car vous ne pouvez jamais les atteindre.

1
jasonharper 16 janv. 2017 à 21:03

Dans les commentaires sur votre question, j'ai suggéré:

@MartijnPieters Peut-être qu'il [OP] veut dire qu'il a besoin d'écrire un programme qui produit une liste potentiellement infinie de listes qui suit un certain modèle.

Vous avez répondu que c'était ce que vous vouliez, alors j'ai essayé - le code que je publie implique l'utilisation d'un générateur de fonctions, que vous pouvez utiliser pour générer une séquence potentiellement sans fin qui suit le modèle que vous spécifier (si nous devions supposer une mémoire infinie).

Il y a peu de temps, j'ai vu une solution incroyable postée par quelqu'un pour générer la séquence des paires coprimes. C'était la première fois que j'avais été mis au courant de tout le concept époustouflant de "générateurs auto-récursifs". Vous pouvez les utiliser pour faire des choses assez impressionnantes, comme générer la séquence Kolakoski.

En tout cas, j'avais l'intuition que je pourrais utiliser des générateurs auto-récursifs pour résoudre votre problème. La bonne nouvelle est que mon code fonctionne. La mauvaise nouvelle est que je n'ai aucune idée du pourquoi mon code fonctionne. C'est ici:

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))

Sortie pour 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'>]]]

Vous pouvez utiliser la variante ci-dessous pour avoir un programme qui continue à générer l'arborescence indéfiniment, en attendant à chaque itération une entrée utilisateur:

if __name__ == '__main__':
    generator = generate_tree()
    while True:
        print(next(generator))
        input()
0
Community 23 mai 2017 à 12:01