Discontinuité dans les index de symboles

[laowantong]

Je constate dans "H3-nbT5-001.json" que les symboles ne sont pas numérotés consécutivement, p. ex. il n'y a pas de symbole n°6.

1. Peux-tu m'expliquer l'intérêt de cette irrégularité ?
2. En supposant que cet intérêt existe, vaut-il de lui sacrifier l'efficacité, la compacité et le principe de moindre surprise d'une numérotation normale ?

[SarahMinich]

Cette irrégularité vient de la façon de générer des inputs, façon qu'Imed m'a demandé de suivre. Ce procédé est le suivant :

• On veut une instance avec t tuiles
• On créé un arbre binaire complet A d'une certaine hauteur, hauteur qui doit être suffisante pour avoir au moins t feuilles
• On choisit aléatoirement t feuilles dans A
• une tuile est un chemin depuis la racine vers une feuille. En choisissant t feuilles, on choisit donc t tuiles
• notre instance est composée des symboles de ces tuiles

[laowantong]

Ok. Est-ce que quelque chose empêche de renuméroter les symboles consécutivement après construction ? C'est une bijection.

Tu comprends bien que si on avait des numéros continus, on n'aurait pas besoin de stocker les numéros des tuiles. Il suffirait d'avoir un tableau avec leurs tailles, les indices jouant le rôle de numéro.

(Et pour peu qu'il n'y ait pas de taille 0, on n'aurait même pas besoin de type ensemble pour les tuiles.)