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

}