Algorithme pour trouver la prochaine permutation supérieure d’une chaîne donnée

Wikipedia a un bel article sur la génération d’ordre lexicographique. Il décrit également un algorithme pour générer la prochaine permutation.

Citant:

L’algorithme suivant génère la prochaine permutation lexicographique après une permutation donnée. Cela change la permutation donnée sur place.

1. Trouve l’indice le plus élevé i tel que s[i] < s[i+1] . Si aucun indice n'existe, la permutation est la dernière permutation.
2. Trouvez le plus haut indice j > i tel que s[j] > s[i] . Un tel j doit exister, puisque i+1 est un tel index.
3. Swap s[i] avec s[j] .
4. Inverser l'ordre de tous les éléments après l'index i jusqu'au dernier élément.

Une excellente solution qui fonctionne est décrite ici: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm . Et la solution qui, si la prochaine permutation existe, la renvoie, sinon retourne false :

 function nextPermutation(array) { var i = array.length - 1; while (i > 0 && array[i - 1] >= array[i]) { i--; } if (i <= 0) { return false; } var j = array.length - 1; while (array[j] <= array[i - 1]) { j--; } var temp = array[i - 1]; array[i - 1] = array[j]; array[j] = temp; j = array.length - 1; while (i < j) { temp = array[i]; array[i] = array[j]; array[j] = temp; i++; j--; } return array; } 

Devoirs? Quoi qu’il en soit, on peut regarder la fonction C ++ std :: next_permutation, ou ceci:

http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html

Nous pouvons trouver la plus grande chaîne lexicographique suivante pour une chaîne donnée S en utilisant l’étape suivante.

 1. Iterate over every character, we will get the last value i (starting from the first character) that satisfies the given condition S[i] < S[i + 1] 2. Now, we will get the last value j such that S[i] < S[j] 3. We now interchange S[i] and S[j]. And for every character from i+1 till the end, we sort the characters. ie, sort(S[i+1]..S[len(S) - 1]) 

La chaîne donnée est la prochaine chaîne lexicographique de S On peut aussi utiliser l' next_permutation fonction next_permutation en C ++.

nextperm (a, n)

 1. find an index j such that a[j….n - 1] forms a monotonically decreasing sequence. 2. If j == 0 next perm not possible 3. Else 1. Reverse the array a[j…n - 1] 2. Binary search for index of a[j - 1] in a[j….n - 1] 3. Let i be the returned index 4. Increment i until a[j - 1] < a[i] 5. Swap a[j - 1] and a[i] O(n) for each permutation. 

 void Solution::nextPermutation(vector &a) { int i,j=-1,k,t=a.size(); for(i=0;i 

}

J’espère que ce code pourrait être utile.

 int main() { char str[100]; cin>>str; int len=strlen(len); int f=next_permutation(str,str+len); if(f>0) { print the ssortingng } else { cout<<"no answer"; } }