1. Introducción
En este artículo, veremos cómo crear permutaciones de una matriz.
Primero, definiremos qué es una permutación. En segundo lugar, veremos algunas limitaciones. Y tercero, veremos tres formas de calcularlos: recursiva, iterativa y aleatoria.
Nos centraremos en la implementación en Java y, por lo tanto, no entraremos en muchos detalles matemáticos.
2. ¿Qué es una permutación?
Una permutación de un conjunto es una reordenación de sus elementos. Un conjunto que consta de n elementos tiene n! permutaciones. ¡Aquí n! es el factorial, que es el producto de todos los números enteros positivos menores o iguales an .
2.1. Ejemplo
La matriz de números enteros [3, 4, 7] tiene tres elementos y seis permutaciones:
¡norte! = 3! = 1 x 2 x 3 = 6
Permutaciones: [3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]
2.2. Restricciones
El número de permutación aumenta rápidamente con n . Si bien solo se necesitan unos segundos para generar todas las permutaciones de diez elementos, se necesitarán dos semanas para generar todas las permutaciones de 15 elementos:
3. Algoritmos
3.1. Algoritmo recursivo
El primer algoritmo que observamos es el algoritmo de Heap. Es un algoritmo recursivo que produce todas las permutaciones intercambiando un elemento por iteración.
Se modificará la matriz de entrada. Si no queremos eso, necesitamos crear una copia de la matriz antes de llamar al método:
public static void printAllRecursive( int n, T[] elements, char delimiter) { if(n == 1) { printArray(elements, delimiter); } else { for(int i = 0; i < n-1; i++) { printAllRecursive(n - 1, elements, delimiter); if(n % 2 == 0) { swap(elements, i, n-1); } else { swap(elements, 0, n-1); } } printAllRecursive(n - 1, elements, delimiter); } } El método utiliza dos métodos auxiliares:
private void swap(T[] input, int a, int b) { T tmp = input[a]; input[a] = input[b]; input[b] = tmp; }private void printArray(T[] input) { System.out.print('\n'); for(int i = 0; i < input.length; i++) { System.out.print(input[i]); } } Aquí, escribimos el resultado en System.out , sin embargo, podemos almacenar fácilmente el resultado en una matriz o en una lista.
3.2. Algoritmo iterativo
El algoritmo de Heap también se puede implementar mediante iteraciones:
int[] indexes = new int[n]; int[] indexes = new int[n]; for (int i = 0; i < n; i++) { indexes[i] = 0; } printArray(elements, delimiter); int i = 0; while (i < n) { if (indexes[i] < i) { swap(elements, i % 2 == 0 ? 0: indexes[i], i); printArray(elements, delimiter); indexes[i]++; i = 0; } else { indexes[i] = 0; i++; } } 3.3. Permutaciones en orden lexicográfico
Si los elementos son comparables, podemos generar permutaciones ordenadas por el orden natural de los elementos:
public static
void printAllOrdered( T[] elements, char delimiter) { Arrays.sort(elements); boolean hasNext = true; while(hasNext) { printArray(elements, delimiter); int k = 0, l = 0; hasNext = false; for (int i = elements.length - 1; i > 0; i--) { if (elements[i].compareTo(elements[i - 1]) > 0) { k = i - 1; hasNext = true; break; } } for (int i = elements.length - 1; i > k; i--) { if (elements[i].compareTo(elements[k]) > 0) { l = i; break; } } swap(elements, k, l); Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length)); } }
Este algoritmo tiene una operación inversa en cada iteración y, por lo tanto, es menos eficiente en matrices que el algoritmo de Heap.
3.4. Algoritmo aleatorio
Si n es grande, podemos generar una permutación aleatoria mezclando la matriz:
Collections.shuffle(Arrays.asList(elements));Podemos hacer esto varias veces para generar una muestra de permutaciones.
Podríamos crear las mismas permutaciones más de una vez; sin embargo, para valores grandes de n , las posibilidades de generar la misma permutación dos veces son bajas.
4. Conclusión
Hay muchas formas de generar todas las permutaciones de una matriz. En este artículo, vimos el algoritmo de Heap recursivo e iterativo y cómo generar una lista ordenada de permutaciones.
No es factible generar todas las permutaciones para matrices grandes, por lo tanto, podemos generar permutaciones aleatorias en su lugar.
La implementación de todos los fragmentos de código de este artículo se puede encontrar en nuestro repositorio de Github.