Algorithme pour trouver la permutation suivante d'une chaîne donnée

Une excellente solution qui fonctionne est décrite ici: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm . et la solution qui, si la permutation suivante 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, peut regarder la fonction c++ std:: next_permutation, ou ceci:

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

Nous pouvons trouver la chaîne lexicographique suivante la plus grande pour une chaîne donnée 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. i.e., sort(S[i+1]..S[len(S) - 1])

La chaîne donnée est la chaîne lexicographique suivante de S. On peut également utiliser next_permutation Appel de fonction 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<int> &a) {    
int i,j=-1,k,t=a.size();
for(i=0;i<t-1;i++)
{
    if(a[i]<a[i+1])
    j=i;
}
if(j==-1)
reverse(a.begin(),a.end());
else
{
for(i=j+1;i<t;i++)
    {
        if(a[j]<a[i])
        k=i;
    }
swap(a[j],a[k]);
reverse(a.begin()+j+1,a.end());
}

}

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 string
    } else {
        cout<<"no answer";
    }
}