Pangramme autodescriptif

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un pangramme autodescriptif est une phrase contenant toutes les lettres de l'alphabet (pangramme) et exprimant une proposition vraie sur elle-même (autodescriptif).

« Ce pangramme autodescriptif en hommage à Douglas Hofstadter, Lee Sallows, Jacques Pitrat, Nicolas Graner et Éric Angelini contient exactement dix-sept a, un b, onze c, huit d, trente-cinq e, cinq f, neuf g, six h, vingt-quatre i, deux j, un k, sept l, six m, vingt-six n, onze o, huit p, huit q, onze r, quinze s, vingt-sept t, dix-sept u, quatre v, deux w, neuf x, un y, et cinq z. »

— OuLiPo[1]

Comment trouver un pangramme autodescriptif ?[modifier | modifier le code]

Le plus simple est d'utiliser un ordinateur, et un sous-programme ou une table qui puisse associer à chaque entier entre 1 (0 si on désire juste une phrase autodescriptive sans exiger que ce soit un pangramme) et par exemple 50 son écriture en toutes lettres. Il suffit alors

  • de tirer au hasard 26 entiers chacun entre 1 et N compris, soit un pour chaque lettre,
  • de faire exprimer en lettres ce que l'on a tiré (« douze a, deux b », etc.),
  • de compter le nombre d'occurrences de chaque lettre, et, s'il n'y a pas conformité, de recommencer l'opération avec ces 26 nouveaux nombres.
  • s'il y a conformité, en revanche, imprimer le résultat.

Méthode empirique[modifier | modifier le code]

Avec un peu de chance, on peut tomber ainsi sur un point fixe. Si on n'en a pas trouvé un au bout de, par exemple, 200 itérations, on peut soupçonner être dans un cycle. Le plus simple est de tirer à nouveau 26 autres valeurs et de retenter sa chance. En laissant travailler sa machine toute la nuit, on trouve quelques pangrammes autodescriptifs le matin en se levant.

Méthodes plus rigoureuses[modifier | modifier le code]

Slow-fast[modifier | modifier le code]

Il existe une méthode de détection de cycle qui se nomme méthode du slow-fast. Elle consiste grosso modo à faire le calcul en double à des vitesses différentes (le tableau A aura par exemple une itération par cycle et le tableau B deux itérations par cycle). Si à un moment quelconque A=B, comme 1 ne peut être égal à 2, cela signifie qu'à coup sûr on est entré dans un cycle.

Signatures[modifier | modifier le code]

On peut calculer pour chaque tableau que l'on obtient une signature (par exemple CRC ou MD5), et conserver à la fois tous les anciens tableaux et toutes les signatures associées. On ne procèdera à une comparaison réelle de tableaux que si leurs signatures sont identiques. Si les tableaux sont également identiques, alors on tire d'autres valeurs pour le calcul.

Cette méthode est plus rapide à mettre en place comme à exécuter que le slow-fast, surtout dans un langage qui comme le Perl possède l'adressage associatif (hashs). Elle consomme davantage de place en mémoire aussi, mais les mémoires actuelles d'un gigaoctet et plus ne rendent pas cette question aussi critique que par le passé.

Notes et références[modifier | modifier le code]