Herramientas de usuario
cpp-avanzado:algorithm:next-permutation
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
cpp-avanzado:algorithm:next-permutation [2017/12/07 15:58] guty [Generar Permutaciones] |
cpp-avanzado:algorithm:next-permutation [2017/12/08 18:22] (actual) guty |
||
|---|---|---|---|
| Línea 1: | Línea 1: | ||
| - | ===== Permutaciones ===== | + | ======= Permutaciones ======= |
| - | FIXME (¿Agregar definición de permutación? ¿noción intuitiva? ¿función biyectiva de un conjunto en sí mismo?) | + | 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: | 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: | ||
| Línea 16: | Línea 16: | ||
| Además, este proceso constructivo da una forma muy natural de escribir un código que calcule todas las permutaciones de 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 ===== | + | ======= Generar Permutaciones ======= |
| - | === Forma 1 (recursiva) === | + | ===== Forma 1 (recursiva) ===== |
| - | Usaremos ''permutacion'' como un vector donde construiremos todas las permutaciones y ''elegido'' como un arreglo booleano (o idealmente un bitset FIXME (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''). | + | 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> | <code cpp> | ||
| Línea 48: | Línea 48: | ||
| </code> | </code> | ||
| - | === Forma 2 (iterativa) === | + | ===== 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: | 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: | ||
| Línea 56: | Línea 56: | ||
| </code> | </code> | ||
| - | Tendremos como resultado que se modificó ''arreglo'' de manera in-place, a la siguiente permutación lexicográfica. Por ejemplo: | + | 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,1,2,3) \xrightarrow{\texttt{next_permutation}} (0,1,3,2)$ |
| - | * $(0,3,1,2) \overset{\texttt{next_permutation}}{\longrightarrow} (0,3,2,1)$ | + | * $(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> | ||
cpp-avanzado/algorithm/next-permutation.1512662305.txt.gz · Última modificación: 2017/12/07 15:58 por guty
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
