Euler 024

Publié le 22/12/16

Former la {N}-ième permutation de « 0123456789 » dans l’ordre lexicographique
(réponse: « 2783915460 » si N=1000000)
  1. Première solution
    • lignes 2 à 6: le générateur perms permet de former les permutations successives d’une chaîne st. On utilise ici un procédé récursif.
      Si la chaîne est de longueur {1}, elle est sa seule permutation.
      Sinon, et si on sait former les permutations d’une chaîne de longueur { < n}, alors pour toute chaîne st de longueur {n}, et pour chacun des caractères c=st[i] de cette chaîne, on forme les permutations de st obtenues en plaçant st[i] devant chacune des permutations de st privées de c.
    • lignes 7 à 10: on incrémente un compteur {n} à chaque production d’une permutation de la chaîne st=’0123456789′. Quand ce compteur atteint la valeur {N}, on renvoie la permutation {p} correspondante.

  2. Deuxième solution Ici on ne va pas générer toutes les permutations de ‘0123456789’ jusqu’à la {N}-ième. En fait, si {st=c_{0}c_{1}\ldots c_{n-1}} est une chaîne de longueur {n\ge 2}, elle possède {n!} permutations: il y a d’abord les {(n-1)!} permutations commençant par {c_{0}}, puis autant débutant par {c_{1}}, etc., et enfin les {(n-1)!} dernières débutant par {c_{n-1}}. La {(N+1)}-ième permutation débute donc par {c_{q}}, où {q} est le quotient dans la division euclidienne de {N} par {(n-1)!}. Si {r} est le reste dans cette division, et pour former la permutation cherchée, il faut alors former la {(r+1)}-ème des permutations de la chaîne {st} privée du caractère {c_{q}}. On en déduit la fonction récursive nthPerm renvoyant la {n}-ième permutation d’une chaîne {st}.

  3. Troisième solution
    Comme dans la deuxième solution, tout repose sur:
    {\begin{array}{rl}N-1&=(n-1)!q_{0}+(n-2)!q_{1}+\cdots\\&+2!q_{n-3}+1!q_{n-2}+q_{n-1}\end{array}}Par exemple, avec {N=10000000}: {\begin{array}{rl}N-1&=2\cdot9!+6\cdot8!+6\cdot7!+2\cdot6!+5\cdot5!\\&+1\cdot4!+2\cdot3!+1\cdot2!+1\cdot1!+0\cdot 0!\end{array}}La permutation de rang {N} de ‘0123456789’ s’écrit donc ‘2662512110’.
    Ici on forme les entiers {q_{k}} par divisions euclidiennes succesives (pas de récursivité) et c’est seulement quand sont connus les {q_{k}} qu’on forme la permutation demandée.