Permutation supérieure suivante

(26 novembre 2020)

Permutation de trois couleurs différentes

Comprenons dabord ce que signifie la permutation. La définition tirée de Wikipédia dit: «  En mathématiques , a permutation dun set est, en gros, un arrangement de ses membres dans une séquence ou ordre linéaire , ou si lensemble est déjà commandé , un réarrangement de ses éléments. Le mot «permutation» fait également référence à lacte ou au processus de changement de lordre linéaire dun ensemble ordonné. »

Ainsi, comme le dit la définition, permutation signifie réorganiser un ensemble dobjets donnés dans toutes les commandes possibles. Comme nous pouvons le voir dans le diagramme ci-dessus, trois couleurs différentes peuvent être arrangées de 6 manières à savoir {RGB, RBG, GRB, GBR, BRG, BGR}.

Une formule mathématique pour calculer le nombre darrangements possibles pour n objets différents est donné par n !, où n! = n * (n-1) * (n-2) *… * 1

Il existe de nombreuses façons de générer systématiquement toutes les permutations dune séquence donnée. Un algorithme classique est basé sur la recherche de la permutation suivante dans lordre lexicographique / dictionnaire / alphabétique, si elle existe.

Donc, lénoncé du problème ici est, on nous donne un ensemble dalphabets peut-être que nous pouvons appelez-le une chaîne, et nous devons trouver le prochain ensemble lexicographique dalphabets ou la prochaine chaîne lexicographique supérieure ou la chaîne qui viendra ensuite dans le dictionnaire après la chaîne actuelle ayant le même ensemble dalphabets que dans la chaîne actuelle.

Prenons un exemple de nombres pour mieux comprendre.

Number = [4,5,2,6,7,3,1]
Le prochain plus grand nombre sera = [4,5,2, 7,1,3,6 ]

Force brute

La première chose qui nous viendra à lesprit est de trouver toutes les permutations du nombre donné et la plus petite de ces permutations qui est également supérieure à notre nombre actuel sera notre réponse. Comme nous lavons vu plus haut, il y en a n! possibilités (n = nombre de chiffres en nombre), en considérant tous les chiffres comme distincts, donc si nous continuons à trouver toutes les permutations pour un nombre donné, il faudra O (n!) temps pour calculer. Cest une lourde complexité de temps si le n est un grand nombre.

Optimisation

Nous devons réfléchir à la manière dont nous pouvons améliorer cela. Si nous observons attentivement, peut-être pour un plus petit ensemble de nombres, nous pourrions voir des modèles. Essayons avec quelques exemples:

[2,1,3] = le nombre supérieur suivant est 231
[1,1,5] = le nombre supérieur suivant est 151
[2,3 , 5,4] = le nombre supérieur suivant est 2435
[3,2,1] = nous ne pouvons pas former un nombre supérieur au nombre actuel à partir de toutes les permutations possibles

À retenir de ce qui précède observation:

Cas 1: [3,2,1]

Ici, nous commençons à nous déplacer de lextrémité droite et essayons de trouver le premier élément décroissant, afin de pouvoir le remplacer par le élément supérieur à lui-même du côté droit de celui-ci.

Cas 1: lélément supérieur suivant nest pas possible en séquence non croissante

Cas 2: [2,3,5,4]

index = 1, index du premier élément décroissant à partir de lextrémité droite
trouver le prochain élément plus grand que 3 dans le côté droit de i = 1, remplacez-le par nums [i]
Maintenant, triez les éléments restants après i = 1 dans lordre croissant pour faire le plus petit élément, nous pouvons simplement inverser les éléments après i = 1 car ils sont déjà triés dans lordre non croissant

Ce graphe prouve quen permutant 4 et 5, la séquence à partir de 8, soit 86432 est toujours triée dans lordre non croissant et cest assez évident car on remplace le premier élément décroissant par lélément qui est juste plus grand quil et donc en conservant lordre non croissant.

Une autre observation que nous pouvons prendre à partir de là est, tout en recherchant lélément suivant plus grand de lindex j = i + 1 à droite, nous pouvons arrêter la recherche à lindex j quand nums [j] devient inférieur ou égal à nums [i], car les éléments après cet index ne peuvent jamais b e supérieur à nums [i].

Extrait de code

Dans le code suivant, au cas où le plus grand suivant la permutation nest pas possible, je la convertis en la plus petite permutation possible

Analyse de complexité

Time Complexity = O (n) { pour trouver le premier élément décroissant dans le pire des cas, par ex. [1,5,4,3,2]} + O (n) {pour trouver le prochain plus grand nombre dans le sous-tableau restant à droite} + O (1) {pour permuter le premier élément décroissant avec le prochain élément plus grand} + O (n / 2) {pour inverser le sous-tableau de i + 1 à len pour trier par ordre croissant} = O (n)

Comme aucun espace supplémentaire nest requis, cela ne prendra pas despace supplémentaire .
Par conséquent, Complexité spatiale: O (1)

Merci de consacrer votre temps à cet article. Jespère que vous le trouverez utile et quil vous donne un aperçu clair.

Si vous avez encore des questions, nhésitez pas à y répondre. Si vous le trouvez utile, partagez-le avec vos collègues. Vos applaudissements me motivent à écrire davantage de tels blogs! 🙂