Permutación de matriz

Por ejemplo, tengo esta matriz:

int a[] = new int[]{3,4,6,2,1}; 

Necesito una lista de todas las permutaciones, de modo que si una es así, {3,2,1,4,6} , otras no deben ser iguales. Sé que si la longitud de la matriz es n, entonces hay n! posibles combinaciones. ¿Cómo se puede escribir este algoritmo?

Actualización: gracias, pero necesito un algoritmo de pseudo código como:

 for(int i=0;i<a.length;i++){ // code here } 

Solo algoritmo Sí, las funciones de la API son buenas, pero no me ayudan demasiado.

Si está usando C ++, puede usar std::next_permutation desde el archivo de encabezado :

 int a[] = {3,4,6,2,1}; int size = sizeof(a)/sizeof(a[0]); std::sort(a, a+size); do { // print a's elements } while(std::next_permutation(a, a+size)); 

Aquí se muestra cómo puede imprimir todas las permutaciones en 10 líneas de código:

 public class Permute{ static void permute(java.util.List arr, int k){ for(int i = k; i < arr.size(); i++){ java.util.Collections.swap(arr, i, k); permute(arr, k+1); java.util.Collections.swap(arr, k, i); } if (k == arr.size() -1){ System.out.println(java.util.Arrays.toString(arr.toArray())); } } public static void main(String[] args){ Permute.permute(java.util.Arrays.asList(3,4,6,2,1), 0); } } 

Tomas el primer elemento de una matriz (k = 0) y lo intercambias con cualquier elemento (i) de la matriz. Luego aplica de forma recursiva la permutación en la matriz comenzando con el segundo elemento. De esta manera, obtienes todas las permutaciones que comienzan con el elemento i-ésimo. La parte difícil es que después de la llamada recursiva debe intercambiar el elemento i-ésimo con el primer elemento, de lo contrario podría obtener valores repetidos en el primer punto. Al intercambiarlo de vuelta, restauramos el orden de los elementos (básicamente, haces un seguimiento).

Iteradores y extensión al caso de valores repetidos

El inconveniente del algoritmo anterior es que es recursivo y no funciona muy bien con los iteradores. Otro problema es que si permite elementos repetidos en su entrada, entonces no funcionará como está.

Por ejemplo, dada la entrada [3,3,4,4] todas las permutaciones posibles (sin repeticiones) son

 [3, 3, 4, 4] [3, 4, 3, 4] [3, 4, 4, 3] [4, 3, 3, 4] [4, 3, 4, 3] [4, 4, 3, 3] 

(si simplemente aplica la función permute desde arriba, obtendrá [3,3,4,4] cuatro veces, y esto no es lo que naturalmente quiere ver en este caso, y el número de tales permutaciones es 4! / (2) ! * 2!) = 6)

Es posible modificar el algoritmo anterior para manejar este caso, pero no se verá bien. Afortunadamente, hay un algoritmo mejor (lo encontré aquí ) que maneja valores repetidos y no es recursivo.

En primer lugar, la permutación de la matriz de cualquier objeto se puede reducir a permutaciones de enteros al enumerarlos en cualquier orden.

Para obtener las permutaciones de una matriz de enteros, comienza con una matriz ordenada en orden ascendente. Tu 'objective' es hacer que descienda. Para generar la siguiente permutación, intenta encontrar el primer índice desde la parte inferior donde la secuencia no puede descender, y mejora el valor en ese índice mientras cambia el orden del rest de la cola de descendente a ascendente en este caso.

Aquí está el núcleo del algoritmo:

 //ind is an array of integers for(int tail = ind.length - 1;tail > 0;tail--){ if (ind[tail - 1] < ind[tail]){//still increasing //find last element which does not exceed ind[tail-1] int s = ind.length - 1; while(ind[tail-1] >= ind[s]) s--; swap(ind, tail-1, s); //reverse order of elements in the tail for(int i = tail, j = ind.length - 1; i < j; i++, j--){ swap(ind, i, j); } break; } } 

Aquí está el código completo de iterador. Constructor acepta una matriz de objetos y los mapea en una matriz de enteros usando HashMap .

 import java.lang.reflect.Array; import java.util.*; class Permutations implements Iterator{ private E[] arr; private int[] ind; private boolean has_next; public E[] output;//next() returns this array, make it public Permutations(E[] arr){ this.arr = arr.clone(); ind = new int[arr.length]; //convert an array of any elements into array of integers - first occurrence is used to enumerate Map hm = new HashMap(); for(int i = 0; i < arr.length; i++){ Integer n = hm.get(arr[i]); if (n == null){ hm.put(arr[i], i); n = i; } ind[i] = n.intValue(); } Arrays.sort(ind);//start with ascending sequence of integers //output = new E[arr.length]; <-- cannot do in Java with generics, so use reflection output = (E[]) Array.newInstance(arr.getClass().getComponentType(), arr.length); has_next = true; } public boolean hasNext() { return has_next; } /** * Computes next permutations. Same array instance is returned every time! * @return */ public E[] next() { if (!has_next) throw new NoSuchElementException(); for(int i = 0; i < ind.length; i++){ output[i] = arr[ind[i]]; } //get next permutation has_next = false; for(int tail = ind.length - 1;tail > 0;tail--){ if (ind[tail - 1] < ind[tail]){//still increasing //find last element which does not exceed ind[tail-1] int s = ind.length - 1; while(ind[tail-1] >= ind[s]) s--; swap(ind, tail-1, s); //reverse order of elements in the tail for(int i = tail, j = ind.length - 1; i < j; i++, j--){ swap(ind, i, j); } has_next = true; break; } } return output; } private void swap(int[] arr, int i, int j){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public void remove() { } } 

Uso / prueba:

  TCMath.Permutations perm = new TCMath.Permutations(new Integer[]{3,3,4,4,4,5,5}); int count = 0; while(perm.hasNext()){ System.out.println(Arrays.toString(perm.next())); count++; } System.out.println("total: " + count); 

Imprime los 7!/(2!*3!*2!)=210 permutaciones.

Aquí hay una implementación de la Permutación en Java:

Permutación – Java

¡Deberías controlarlo!

Editar: código pegado debajo para proteger contra link-death:

 // Permute.java -- A class generating all permutations import java.util.Iterator; import java.util.NoSuchElementException; import java.lang.reflect.Array; public class Permute implements Iterator { private final int size; private final Object [] elements; // copy of original 0 .. size-1 private final Object ar; // array for output, 0 .. size-1 private final int [] permutation; // perm of nums 1..size, perm[0]=0 private boolean next = true; // int[], double[] array won't work :-( public Permute (Object [] e) { size = e.length; elements = new Object [size]; // not suitable for primitives System.arraycopy (e, 0, elements, 0, size); ar = Array.newInstance (e.getClass().getComponentType(), size); System.arraycopy (e, 0, ar, 0, size); permutation = new int [size+1]; for (int i=0; ipermutation[i+1]) i--; if (i==0) { next = false; for (int j=0; jpermutation[j]) j--; swap (i,j); int r = size; int s = i+1; while (r>s) { swap(r,s); r--; s++; } return ar; } public String toString () { final int n = Array.getLength(ar); final StringBuffer sb = new StringBuffer ("["); for (int j=0; j 

Esto es una permutación de 2 para una lista envuelta en un iterador

 import java.util.Iterator; import java.util.LinkedList; import java.util.List; /* all permutations of two objects * * for ABC: AB AC BA BC CA CB * * */ public class ListPermutation implements Iterator { int index = 0; int current = 0; List list; public ListPermutation(List e) { list = e; } public boolean hasNext() { return !(index == list.size() - 1 && current == list.size() - 1); } public List next() { if(current == index) { current++; } if (current == list.size()) { current = 0; index++; } List output = new LinkedList(); output.add(list.get(index)); output.add(list.get(current)); current++; return output; } public void remove() { } } 

Hay n! permutaciones totales para el tamaño de matriz dado n . Aquí hay un código escrito en Java usando DFS.

 public List> permute(int[] nums) { List> results = new ArrayList>(); if (nums == null || nums.length == 0) { return results; } List result = new ArrayList<>(); dfs(nums, results, result); return results; } public void dfs(int[] nums, List> results, List result) { if (nums.length == result.size()) { List temp = new ArrayList<>(result); results.add(temp); } for (int i=0; i 

Para la matriz de entrada [3,2,1,4,6], ¡hay 5 totalmente! = 120 posibles permutaciones que son:

 [[3,4,6,2,1],[3,4,6,1,2],[3,4,2,6,1],[3,4,2,1,6],[3,4,1,6,2],[3,4,1,2,6],[3,6,4,2,1],[3,6,4,1,2],[3,6,2,4,1],[3,6,2,1,4],[3,6,1,4,2],[3,6,1,2,4],[3,2,4,6,1],[3,2,4,1,6],[3,2,6,4,1],[3,2,6,1,4],[3,2,1,4,6],[3,2,1,6,4],[3,1,4,6,2],[3,1,4,2,6],[3,1,6,4,2],[3,1,6,2,4],[3,1,2,4,6],[3,1,2,6,4],[4,3,6,2,1],[4,3,6,1,2],[4,3,2,6,1],[4,3,2,1,6],[4,3,1,6,2],[4,3,1,2,6],[4,6,3,2,1],[4,6,3,1,2],[4,6,2,3,1],[4,6,2,1,3],[4,6,1,3,2],[4,6,1,2,3],[4,2,3,6,1],[4,2,3,1,6],[4,2,6,3,1],[4,2,6,1,3],[4,2,1,3,6],[4,2,1,6,3],[4,1,3,6,2],[4,1,3,2,6],[4,1,6,3,2],[4,1,6,2,3],[4,1,2,3,6],[4,1,2,6,3],[6,3,4,2,1],[6,3,4,1,2],[6,3,2,4,1],[6,3,2,1,4],[6,3,1,4,2],[6,3,1,2,4],[6,4,3,2,1],[6,4,3,1,2],[6,4,2,3,1],[6,4,2,1,3],[6,4,1,3,2],[6,4,1,2,3],[6,2,3,4,1],[6,2,3,1,4],[6,2,4,3,1],[6,2,4,1,3],[6,2,1,3,4],[6,2,1,4,3],[6,1,3,4,2],[6,1,3,2,4],[6,1,4,3,2],[6,1,4,2,3],[6,1,2,3,4],[6,1,2,4,3],[2,3,4,6,1],[2,3,4,1,6],[2,3,6,4,1],[2,3,6,1,4],[2,3,1,4,6],[2,3,1,6,4],[2,4,3,6,1],[2,4,3,1,6],[2,4,6,3,1],[2,4,6,1,3],[2,4,1,3,6],[2,4,1,6,3],[2,6,3,4,1],[2,6,3,1,4],[2,6,4,3,1],[2,6,4,1,3],[2,6,1,3,4],[2,6,1,4,3],[2,1,3,4,6],[2,1,3,6,4],[2,1,4,3,6],[2,1,4,6,3],[2,1,6,3,4],[2,1,6,4,3],[1,3,4,6,2],[1,3,4,2,6],[1,3,6,4,2],[1,3,6,2,4],[1,3,2,4,6],[1,3,2,6,4],[1,4,3,6,2],[1,4,3,2,6],[1,4,6,3,2],[1,4,6,2,3],[1,4,2,3,6],[1,4,2,6,3],[1,6,3,4,2],[1,6,3,2,4],[1,6,4,3,2],[1,6,4,2,3],[1,6,2,3,4],[1,6,2,4,3],[1,2,3,4,6],[1,2,3,6,4],[1,2,4,3,6],[1,2,4,6,3],[1,2,6,3,4],[1,2,6,4,3]] 

Espero que esto ayude.

Ejemplo con matriz primitiva:

 public static void permute(int[] intArray, int start) { for(int i = start; i < intArray.length; i++){ int temp = intArray[start]; intArray[start] = intArray[i]; intArray[i] = temp; permute(intArray, start + 1); intArray[i] = intArray[start]; intArray[start] = temp; } if (start == intArray.length - 1) { System.out.println(java.util.Arrays.toString(intArray)); } } public static void main(String[] args){ int intArr[] = {1, 2, 3}; permute(intArr, 0); } 

Representación visual de la solución recursiva de 3 elementos: http://www.docdroid.net/ea0s/generatepermutations.pdf.html

Descompostura:

  1. Para una matriz de dos elementos, hay dos permutaciones:
    • La matriz original, y
    • Los dos elementos intercambiados
  2. Para una matriz de tres elementos, hay seis permutaciones:
    • Las permutaciones de los dos elementos inferiores, luego
    • Cambie los elementos primero y segundo y las permutaciones del elemento inferior dos
    • Cambie los elementos primero y tercero, y las permutaciones de los dos elementos inferiores.
    • Esencialmente, cada uno de los artículos tiene su oportunidad en el primer tragamonedas

Una implementación java simple, consulte c ++ std::next_permutation :

 public static void main(String[] args){ int[] list = {1,2,3,4,5}; List> output = new Main().permute(list); for(List result: output){ System.out.println(result); } } public List> permute(int[] nums) { List> list = new ArrayList>(); int size = factorial(nums.length); // add the original one to the list List seq = new ArrayList(); for(int a:nums){ seq.add(a); } list.add(seq); // generate the next and next permutation and add them to list for(int i = 0;i < size - 1;i++){ seq = new ArrayList(); nextPermutation(nums); for(int a:nums){ seq.add(a); } list.add(seq); } return list; } int factorial(int n){ return (n==1)?1:n*factorial(n-1); } void nextPermutation(int[] nums){ int i = nums.length -1; // start from the end while(i > 0 && nums[i-1] >= nums[i]){ i--; } if(i==0){ reverse(nums,0,nums.length -1 ); }else{ // found the first one not in order int j = i; // found just bigger one while(j < nums.length && nums[j] > nums[i-1]){ j++; } //swap(nums[i-1],nums[j-1]); int tmp = nums[i-1]; nums[i-1] = nums[j-1]; nums[j-1] = tmp; reverse(nums,i,nums.length-1); } } // reverse the sequence void reverse(int[] arr,int start, int end){ int tmp; for(int i = 0; i <= (end - start)/2; i++ ){ tmp = arr[start + i]; arr[start + i] = arr[end - i]; arr[end - i ] = tmp; } } 

Hazlo así…

 import java.util.ArrayList; import java.util.Arrays; public class rohit { public static void main(String[] args) { ArrayList a=new ArrayList(); ArrayList b=new ArrayList(); b.add(1); b.add(2); b.add(3); permu(a,b); } public static void permu(ArrayList prefix,ArrayList value) { if(value.size()==0) { System.out.println(prefix); } else { for(int i=0;i a=new ArrayList(); a.addAll(prefix); a.add(value.get(i)); ArrayList b=new ArrayList(); b.addAll(value.subList(0, i)); b.addAll(value.subList(i+1, value.size())); permu(a,b); } } } }