Si vous décrivez brièvement l'ordre lexicographique, il s'agit d'un tri par ordre alphabétique. C'est-à-dire la séquence de caractères - AAA → AAB → AAC → AAD → ……… → WWW - est triée par ordre alphabétique (ou dans notre cas lexicographique).
Imaginez que vous ayez une séquence finie de caractères, par exemple 0, 1, 2, 5, 3, 3, 0 et que vous ayez besoin de trouver toutes les permutations possibles de ces caractères. Le plus intuitif, mais aussi le plus difficile, est l'algorithme récursif, lorsque nous sélectionnons le premier caractère de la séquence, puis sélectionnons récursivement le deuxième, le troisième, etc., jusqu'à ce que tous les caractères de la séquence soient sélectionnés. Il est clair que la complexité d'un tel algorithme est O (n!).
Mais il s'avère que l'algorithme le plus simple pour générer toutes les permutations dans l'ordre lexicographique est de commencer par la plus petite et de calculer à plusieurs reprises la prochaine permutation en place. Voyons comment faire.
Tout comme lors du calcul de la prochaine valeur entière, nous devons essayer d'augmenter le côté droit de la séquence et de laisser le côté gauche inchangé.
À titre d'exemple, prenez la séquence ci-dessus - (0, 1, 2, 5, 3, 3, 0). Pour obtenir une séquence plus élevée que celle d'origine, il suffit de réorganiser les premier et deuxième éléments par endroits, mais cela n'est pas nécessaire, car vous pouvez réorganiser les deuxième et troisième éléments et obtenir une séquence plus proche dans l'ordre croissant. ce qui nous conduira à la prochaine permutation plus proche, etc.
L'algorithme le plus optimal dans ce cas serait le suivant:
- Tout d'abord, vous devez trouver le plus grand suffixe non croissant. Dans l'exemple ci-dessus, ce serait - (5, 3, 3, 0). Si vous essayez de faire une permutation dans cette séquence, elle ne sera pas supérieure à celle d'origine.
Il vaut la peine de dire que vous pouvez trouver cette séquence en temps O (n) en regardant la séquence de gauche à droite. - L'élément suivant du suffixe est le point de pivot. Dans notre cas, c'est 2. Le point de pivot sera toujours inférieur au premier élément du suffixe. Cela signifie que dans le suffixe, il y aura certainement un élément dépassant le point de pivot et si nous changeons le point de pivot pour le plus petit élément du suffixe dépassant l'élément de support du point de pivot - nous obtiendrons une séquence dépassant l'original - dans notre cas, ce sera (0, 1, 3, 5 , 3, 2, 0).
C'est-à-dire le résultat de cette opération sera le préfixe ascendant minimum possible.
- Et dans la dernière étape, nous devons trier le suffixe dans l'ordre croissant. C'est-à-dire nous obtenons le suffixe le plus petit possible. Dans notre exemple, ce sera (0, 2, 3, 5) et la séquence entière ressemblera à (0, 1, 3, 0, 2, 3, 5).
Cette valeur sera le
prochain réarrangement lexicographique.
Quant à l'application pratique de l'algorithme, pendant tout le temps de mon travail, je n'en ai jamais eu besoin, mais pour une interview avec Uber, ils ont pensé le contraire :))
Par souci de simplicité, tout le code sera écrit en Go, et je pense qu'il est facile pour quiconque de le traduire dans n'importe quel autre langage de programmation.Un grand merci à PYXRU et 646f67 pour m'avoir poussé avec un nez dans une optimisation possible de l'algorithme - pour calculer la permutation pour la complexité linéaire simplement en faisant le suffixe inverse.
func NextPermutationAlgorithm(w string) string { l := len(w) b := []byte(w) r := "no answer" for i:=l-1; i>0 ; i--{ if b[i-1] < b[i] { pivot := i for j := pivot; j < l; j++ { if b[j] <= b[pivot] && b[i-1] < b[j] { pivot = j } } b[i-1], b[pivot] = b[pivot], b[i-1] for j := l-1; i < j; i, j = i+1, j-1 { b[i], b[j] = b[j], b[i] } r = string(b) break } } return r }