Permutation circulaire lexicographiquement minimale

En informatique, et notamment en algoritmique du texte la permutation circulaire lexicographiquement minimale d'une chaîne de caractères est la permutation circulaire d'une chaîne de caractères qui, pour un ordre ordre lexicographique donné, est la permutation minimale parmi toutes les permutations circulaires.

Par exemple, la permutation circulaire minimale de ${\displaystyle bbaaccaadd}$ est ${\displaystyle aaccaaddbb}$. La permutation circulaire minimale permet une représentation normalisée des chaînes. Elle facilite la vérification de l'égalité des chaînes circulaires^[1].

L'algorithme naïf pour trouver la permutation circulaire lexicographique minimale d'une chaîne consiste à parcourir les permutations successives tout en gardant une trace de la permutation lexicographique la plus minimale rencontrée. Si la chaîne est de longueur n, cet algorithme s'exécute en O(n²) temps dans le pire des cas.

Un algorithme efficace a été proposé par Booth en 1980^[2]. L'algorithme utilise une fonction de prétraitement modifiée de celle employée dans l'algorithme de Knuth-Morris-Pratt. La fonction d'échec de la chaîne est calculée normalement, mais la chaîne est permutée circulairement pendant le calcul, de sorte que certains indices doivent être calculés plus d'une fois lors de la rotation. La permutation lexicographique minimale est obtenue à la fin du calcul et l'indice de départ est renvoyé. La démonstration de l'exactitude de l’algorithme est un peu difficile à comprendre, mais sa mise en œuvre est facile. Voici une implémentation en python :

.

def least_rotation(s: str) -> int:
  n = len(s)
  f = [-1] * (2 * n)
  k = 0
  for j in range(1, 2 * n):
    i = f[j - k - 1]
    while i != -1 and s[j % n] != s[(k + i + 1) % n]:
      if s[j % n] < s[(k + i + 1) % n]:
        k = j - i - 1
      i = f[i]
    if i == -1 and s[j % n] != s[(k + i + 1) % n]:
      if s[j % n] < s[(k + i + 1) % n]:
        k = j
      f[j - k] = -1
    else:
      f[j - k] = i + 1
  return k

La suppression des lignes de code qui modifient la valeur de k donne la fonction de prétraitement de Knuth-Morris-Pratt d'origine, car le nombre k qui représentant le décalage de la rotation reste constamment nul. L'algorithme de Booth opère en temps ${\displaystyle O(n)}$ pour une chaîne de longueur ${\displaystyle n}$. L'algorithme effectue au plus ${\displaystyle 3n}$ et nécessite une mémoire auxiliaire de longueur ${\displaystyle n}$.

Shiloach (1981)^[3] a proposé en 1981 un algorithme améliorant le résultat de Booth en termes de performance. Il observe que s'il existe q permutation circulaires lexicographiquement minimales équivalentes d'une chaîne de longueur n, alors la chaîneest constituée de q sous-chaînes égales de longueur ${\displaystyle d=n/q}$. L'algorithme ne nécessite que ${\displaystyle n+d/2}$ comparaisons et espace constant dans le pire des cas.

L'algorithme est divisé en deux phases. Dans la première phase, un criblage rapide élimine les indices qui ne sont manifestement pas des indices de départ pour la permutation circulaire lexicographique minimale. La deuxième phase détermine ensuite l'indice de début de rotation lexicographiquement minimale à partir des indices restants.

Duval (1983)^[4] a donné un algorithme efficace qui factorise la chaîne en ses facteurs qui sont des mots de Lyndon. L'algorithme s'exécute en temps linéaire avec place en mémoire constante.

Shiloach (1979)^[5] a proposé un algorithme permettant de tester efficacement l'égalité de deux chaînes circulaires sans normalisation. Une application supplémentaire qui découle de l’algorithme est la génération rapide de certaines structures chimiques sans répétitions.

• Mot de Lyndon
• Algorithme de Knuth-Morris-Pratt
• Suite de de Bruijn
• mot circulaire

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lexicographically minimal string rotation » (voir la liste des auteurs).

• Portail des mathématiques
• Portail de l'informatique théorique