Où puis-je trouver un structure d'arbre ?

Bonjour à tous, je suis en train d'implémenter une manière de créer des mélanges de rubik's cube pour ne pas avoir de doublons, qui soit rapide et en même temps que je puisse sauvegarder sur disque. J'ai pensé utiliser un arbre (avec quelques règles qui n'ont d'intérêt que si vous souhaitez en savoir plus). Sauf qu'à ma grande surprise il n'existe visiblement pas de structure d'arbre "populaire" dans le monde python, et celle que j'ai trouvé ne semblent pas correspondre à ce que je souhaite.

Les mélanges de rubik's cube peuvent être vus comme des mots (enchaînement de 18 caractères différents). Toute les structures déjà présente et populaire que j'ai vu (SO surtout) permettent de créer des arbres en indiquant le parent, sauf que dans mon cas désigner un parent n'est simplement pas possible puisqu'un sommet nommé A existe en plusieurs fois (en fait il existe $15^{profondeur-1}, profondeur > 1$ par niveau).

Du coup ma question est : connaissez-vous quelque chose qui fasse ce que je cherche ou dois-je l'implémenter moi même ? Et petite question bonus (je n'ai pas cherché), est-ce aussi simple de faire une sérialisation qu'en java ?

Merci d'avance

Hello,

Plutôt que de répondre au problème que tu penses avoir, je vais tenter de répondre au problème d'origine.

J'ai du mal à comprendre où tu veux en venir avec ton arbre de mélange des Rubik's cube. Il y a environ $43\cdot 10^{18}$ mélanges uniques possibles du Rubik's cube (et on peut montrer qu'ils sont tous accessibles en au plus 21 mouvements, note que $21^{18}\approx 6.3\cdot 10^{23}$ donc en gros, 99.99% des suites de 21 mouvements sont "inutiles").

Bref, même avec la structure de données la mieux pensée au monde pour ce problème, tu n'arriveras pas à faire tenir ça en RAM, ni même avec ce qui se fait de mieux en matière de stockage (il t'en faudrait 100000 comme ça…).

Il faudrait que tu sois plus clair sur ce que tu souhaites faire…

Mon but n'est pas du tout de générer tout les mélanges, c'est assez simple mais long et instockable. Ce que je souhaite c'est générer un certain nombre de mélange pour chaque coup possible qui soient uniques (c'est important). Ensuite si je veux récupérer mes mélanges je n'ai plus qu'à lire les feuilles d'une certaine profondeur puis remonter jusqu'à la racine pour connaître le mélange complet. C'est pour ça que j'ai pensé à un arbre, à l'image des dictionnaires. Sauf que je vais générer l'arbre moi même (pas entièrement bien sûr, juste ce dont j'ai besoin). A termes j'aurais besoin de 2-3 millions de mélanges (avec plus de 20 mouvements, l'idée n'est pas d'être optimal mais bien d'avoir des mélanges différents).

J'espère t'avoir un peu plus éclairé sur ce que je voulais faire, sinon hésite pas

Euh… Statistiquement, si tu fais 10 millions de mélanges de 21 mouvements aléatoirement, la probabilité qu'ils soient tous différents sera de l'ordre de $(1-10^{-19})^{10^7}\approx 1-10^{-12}$ (en ordre de grandeur, tu as 10000 fois plus de chances de gagner le gros lot au loto que d'avoir deux mélanges identiques). Autrement dit, tu n'as pas besoin de te prendre la tête avec un arbre, tu as juste à générer une liste du nombre de mélanges qu'il te faut (ou même utiliser un générateur plutôt qu'une liste pour ne pas te les trainer tous en mémoire si t'en as pas besoin), ils seront tous différents. Tu te poses un faux problème.

Oui, sauf que j'ai besoin de faire ça pour des mélanges de tout les nombres de coups (entre 1 et 20). Parce qu'effectivement, pour un certains nombre de coup suffisamment grand (au dessus de 5 en fait), ça ne pose plus de problème, en dessous plus.

Mais bon, je vais faire autrement visiblement.

Et même si je change de méthode, on peut quand même répondre à ma question initiale, au moins par curiosité. Comment est-ce qu'on ferait pour générer des arbres qui pourrait être associés à des dictionnaires (au sens français du mot, pas informatique) ? Parce que les lib que j'ai trouvé demande que le nom des feuilles soient uniques, ce qui est complètements contradictoire avec la notion d'alphabet et de mots.