algorithm - para - permutacion de numeros en c++

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

¿Deberes? De todos modos, puede ver la función de C ++ std :: next_permutation, o esto:

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

Answer 2

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 3

Podemos encontrar la siguiente cadena lexicográfica más grande para una cadena S dada 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áfica más grande de S También se puede usar la next_permutation función next_permutation en C ++.

Answer 4

Una gran solución que funciona se describe aquí: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm . Y la solución que, si la próxima permutación existe, la 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 5

Wikipedia tiene un buen article sobre 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. Encuentre el índice más alto i tal que s[i] < s[i+1] . Si no existe tal índice, la permutación es la última permutación.
2. Encuentre el índice más alto j > i tal que s[j] > s[i] . Tal j debe existir, ya que i+1 es ese índice.
3. Intercambia s[i] con s[j] .
4. Invierta el orden de todos los elementos después del índice i hasta el último elemento.

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.

Answer 7

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());
}

}