OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
======= Permutaciones =======

FIXME (¿Agregar definición de permutación? ¿noción intuitiva? ¿función biyectiva de un conjunto en sí mismo? Por ahora queda el link a wikipedia)[[https://es.wikipedia.org/wiki/Permutaci%C3%B3n|Permutación Wikipedia]]

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. 

======= Generar Permutaciones ======= 

===== Forma 1 (recursiva) =====

Usaremos ''permutacion'' como un vector donde construiremos todas las permutaciones y ''elegido'' como un arreglo booleano (o idealmente un [[cpp-avanzado:bitset|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'').

<code cpp>

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

</code>

===== Forma 2 (iterativa) =====

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:

<code cpp>
   next_permutation(arreglo.begin(),arreglo.end());
</code>

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)   \xrightarrow{\texttt{next_permutation}} (0,1,3,2)$ 
   * $(0,3,1,2)   \xrightarrow{\texttt{next_permutation}} (0,3,2,1)$ 
   * $(0,2,1,1,3) \xrightarrow{\texttt{next_permutation}} (0,2,1,3,1)$ 
   * $(0,3,2,1,1) \xrightarrow{\texttt{next_permutation}} (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 [[cpp-avanzado:algorithm:sort | sort]]   en el arreglo), y luego ejecutar el siguiente código.

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

</code>
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
