• Sous-ensembles d'un ensemble
• Arbres (binaires ou autres...)
• Graphes
• Permutations

• Boucler sur toutes les structures
• Stocker une structure dans l'espace minimum possible (code)
• Récupérer une structure stockée (décode)
• Compter les structures
• Stocker des informations sur toutes dans un tableau

• Sous-ensemble de n objets ≈ entier en 0…2ⁿ-1
• Permutation? considérer une permutation comme n entiers en 0…n-1 donnerait une représentation par un entier en 0…nⁿ-1
• Mais tous ces entiers ne correspondent pas à une permutation (nⁿ entiers mais n! permutations)
• Interpréter suite a₁, a₂, …, a_n avec 1 < =a_i < =i: échanger les éléments n et a_n, ensuite n-1 et a_n-1 et ainsi de suite; chaque permutation est générée une seule fois
• Facile à générer la suite des a à partir d'un entier en 0…n!-1
• (Remarquer l'existence d'algorithmes plus astucieux qui générent toutes les permutations avec une seule transposition à chaque itération)

• Pour toute taille i possible du sous-arbre gauche (0…n-1)
• générer tous les sous-arbres gauches (taille i)i
• générer tous les sous-arbres droits (taille n-1-i)
• mais complication de programmation; il faut chaque combinaison possible d'un sous-arbre gauche et droit; donc, on pourrait stocker deux listes des sous-arbres gauches et droites et les croiser; mais solution trop gourmande en espace
• une solution possible: procédures/fonctions init et prochain
  init donne le premier arbre (d'une taille donnée) et prochain(T) donne le successeur de T dans la liste
  définies récursivement!

  par exemple: prochain(T)=
  (T^.gauche, prochain(T^.droite) si le prochain n'échoue pas
  ou prochain(T^.gauche), init(taille(T^.droite))) si ...
  ou init(taille(T^.gauche)+1), init(taille(T^.droite)-1)) si taille(T^.droite) > 0
  ou échoue
  et init(n) est une chaîne à droite.

• Soit T(n) le nombre d'arbres de taille n
• Considérer le nombre avec sous-arbre gauche de taille i
• T(n)=∑_i=0^n-1T(i)*T(n-1-i)
• Programmation dynamique!
• T(0)=1

• Ordonner les arbres selon la taille de leur sous-arbre gauche, et ensuite selon le code de ce sous-arbre et enfin le code du sous-arbre droite
• code(A)=∑_i=0^{taille(A.gauche)-1}T(i)*T(n-1-i)+code(A.gauche)*T(A.droite)+code(A.droite)
• code(arbre.vide)=0

• La taille du sous-arbre gauche (min i tel que la somme est au moins c)
• Le code du sous-arbre gauche ((c-la somme)/T(A.droite))
• Le code du sous-arbre droit (et le reste de la division)
• Et continuer récursivement

• Ordonner les objets selon les choix faits par l'algorithme
• considérer le nombre d'objets susceptibles d'être générés par chaque choix
  il faut que ce nombre soit calculable efficacement
• ajouter pour coder
• soustraire pour décoder

Par exemple de vrais arbres (selon les matheux, pas les arbres binaires des informaticiens)

• Arbre = vide ou racine + ensemble de sous-arbres
• ensemble, donc sans ordre
• pour simplifier, je considère les cas de degré max 2
• Alors, un arbre peut être representé par un arbre binaire
• Mais, de plusieurs façons! (à cause de l'ordre des sous-arbres)

• Quand une structure a plusieurs représentations, on en choisit arbitrairement une comme la ``vraie'' ou canonique
• Par exemple ordonner les arbres (binaires) par taille, sous-arbre gauche, sous-arbre droit
• et dire que la rep. canonique d'un arbre est le premier arbre binaire qui en est une représentation
• Fonction de décider si une rep. est canonique
• Récurrence pour le nombre d'arbres de taille n (n > 1): G(n) = G(n-1)
  + ∑_i=1 ^{n/2 -1} G(i)*G(n-1-i) +
  (si n impair)G((n-1)/2) + (

  G((n-1)/2)

  2

  )
  (à noter: arrondir vers le bas dans la division n/2)
  (les quatre parties sont: un seul sous-arbre (forcément de taille n-1, deux sous-arbres de taille différente, le plus petit de taille i, deux sous-arbres identiques, deux sous-arbres différents de la même taille)
• Mêmes principes pour codage et décodage

• graphes sur n sommets de degré maximum (par exemple) 3
• On peut les générer en considérant chaque sommet à son tour et ajoutant un nombre d'arêtes jusqu'à 3 - degré actuel
• mais contraintes: pas d'arête à un sommet qui a déjà degré 3
• donc, combien de façons de compléter?

• donc, on veut générer (ou compter) un representant canonique de chaque classe d'équivalence
• mais les classes ne sont pas toutes de la même taille!
• difficile même de savoir si une structure est canonique
• ou de décider si deux structures sont isomorphes (Pb NP-complet)