(¿Agregar definición de permutación? ¿noción intuitiva? ¿función biyectiva de un conjunto en sí mismo?)

Dado un arreglo de $n$ elementos (sus índices se encuentran en $\left \{0,1, \dots, n-1 \right \}$), se plantea el problema de hallar todas las permutaciones del mismo. Ejemplo, si $n=3$, todas las permutaciones posibles de $\left \{ 0,1,2 \right \}$ son:

• 1: $(0,1,2)$
• 2: $(0,2,1)$
• 3: $(1,0,2)$
• 4: $(1,2,0)$
• 5: $(2,0,1)$
• 6: $(2,1,0)$

En general, dado un conjunto de $n$ elementos, tenemos $n!$ permutaciones posibles. Esto se ve claramente si uno piensa en el proceso de construcción de una permutación. El primer elemento puede ser cualquiera de los $n$ posibles, para el segundo hay $n-1$ opciones, pues podrá tener cualquier valor a excepción del valor elegido para el primer elemento, y así sucesivamente. De esta forma se ve que hay $n! = n(n-1)\cdots1$ permutaciones posibles para un arreglo.

Además, este proceso constructivo da una forma muy natural de escribir un código que calcule todas las permutaciones de un arreglo.

Usaremos permutacion como un vector donde construiremos todas las permutaciones y elegido como un arreglo booleano (o idealmente un bitset (agregar link a bitset)), que nos dirá en la $i$-ésima posición, si el $i$-ésimo elemento ya fue elegido en el proceso constructivo de la permutación (y es un elemento actual de permutacion).

void generarPermutaciones()
{
   if (permutacion.size() == n)
   {
      // hacemos lo que queremos con la permutacion armada
   }
   else
   {
      for(int i = 0; i < n; i++) // iteramos todos los candidatos a agregar en la permutacion
      {
         if (!elegido[i])
         {
            elegido[i] = true; // lo marcamos para no elegirlo nuevamente en el proceso
            permutacion.push_back(i); // lo agregamos a la permutacion
            generarPermutaciones(); // seguimos el proceso de construccion
            elegido[i] = false; // lo desmarcamos como elegido
            permutacion.pop_back(); // lo sacamos de la permutacion actual
         }
      }
   }
}

Otra forma de generar todas las permutaciones eficientemente es utilizar la función next_permutation que viene implementada en la librería estándar de C++. Si uno tiene un arreglo de $n$ elementos, y estos elementos pueden compararse con el operador $<$ (es decir está implementado el operator < para el tipo de los elementos del arreglo en cuestión), entonces al escribir:

   next_permutation(arreglo.begin(),arreglo.end());

Tendremos como resultado que se modificó arreglo de manera in-place, a la siguiente permutación lexicográfica (que sea distinta a la original, esto cobra importancia si tenemos elementos repetidos). Por ejemplo:

• $(0,1,2,3) \overset{\texttt{next_permutation}}{\longrightarrow} (0,1,3,2)$
• $(0,3,1,2) \overset{\texttt{next_permutation}}{\longrightarrow} (0,3,2,1)$
• $(0,2,1,1,3) \overset{\texttt{next_permutation}}{\longrightarrow} (0,2,1,3,1)$
• $(0,3,2,1,1) \overset{\texttt{next_permutation}}{\longrightarrow} (1,0,1,2,3)$

De esta forma, si queremos generar todas las permutaciones de un arreglo, debemos comenzar con la permutación lexicográficamente más chica (por ejemplo, llamando a sort (agregar link a sort) en el arreglo), y luego ejecutar el siguiente código.

do
{
   // Hacemos lo que queremos con la permutacion
} while (next_permutation(arreglo.begin(),arreglo.end()));