2012-05-09 9 views
5

es que hay una manera fácil de hacer next_permutation para realizar un mismo conjunto de permutas de dos matrices diferentes del mismo tamaño por ejemplo si tengo dos matrices a[]={1,2,3,4,5} y b[]={12,23,21,2,3} si después de la permutación 1 en la matriz a va a la 3 ° posición, luego 12 en la matriz b también debe ir a la 3 ° posición.mismas permutaciones en dos matrices usando next_permutation() STL en C++

Respuesta

4

Usted puede hacer un conjunto de índices auxiliares:

int a[] = { 1, 2, 3, 4, 5 }; 
int b[] = { 12, 23, 21, 2, 3 }; 

std::size_t indices[] = { 0, 1, 2, 3, 4 }; 

Ahora realice las permutaciones en indices, y luego utilice a[indices[i]] y b[indices[i]].

1

Tenga en cuenta que std :: next_permutation no mantiene ningún estado (iría en contra del concepto de algoritmos stl). Entonces, ¿cómo genera la próxima permutación? Lo hace por el orden de los elementos. Es por eso que hay una versión que acepta un operador de comparación

Si le da una matriz ordenada de tamaño N, ¡next_permutation se puede llamar N! veces. De lo contrario, tiene menos permutaciones antes de que el algoritmo devuelva falso.

Para responder a su pregunta, si las matrices tienen el mismo orden en términos del "conjunto de índices auxiliares" como se sugirió anteriormente, entonces los mismos elementos se intercambiarán.

Ejemplo:

int a[] = { 1, 2, 4, 3 }; 
int b[] = { 11, 12, 14, 13 }; 

Estos se permutan el mismo, porque especie producirá el mismo orden de índice.