Algoritmo para encontrar la siguiente mayor permutación de una cadena dada

Question

Quiero un algoritmo eficiente para encontrar la siguiente mayor permutación de la cadena dada.

Answer 1

Wikipedia tiene un buen article en la generación de orden lexicográfico. También describe un algoritmo para generar la siguiente permutación.

Citando:

El siguiente algoritmo genera la siguiente permutación lexicográficamente después de una permutación dada. Cambia la permutación dada en el lugar.

1. Encuentra el mayor índice i tal que s[i] < s[i+1]. Si no existe tal índice, la permutación es la última permutación.
2. Encuentra el índice más alto j > i tal que s[j] > s[i]. Tal j debe existir, ya que i+1 es dicho índice.
3. Intercambio s[i] con s[j].
4. Invierta el orden de todos los elementos después del índice i hasta el último elemento.

Answer 2

¿Deberes? De todos modos, puede mirar en el C++ función std :: next_permutation, o esto:

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

Answer 3

Podemos encontrar la siguiente cadena más grande lexicográfico para una cadena dada S utilizando el siguiente paso.

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 cadena dada es la siguiente cadena lexicográfico más grande de S. También se puede usar la llamada a la función next_permutation en C++.

Answer 4

Espero que este código pueda ser útil.

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"; 
    } 
} 

Answer 5

Una gran solución que funciona se describe aquí: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm. Y la solución que, si existe al lado de permutación, lo devuelve, de lo contrario devuelve 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; 
} 

Answer 6

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.