Algoritmo de permutación para una matriz de enteros en Java

Tengo un ejemplo de trabajo para generar todas las permutaciones de caracteres en una cadena como a continuación:

static ArrayList permutations(String s) { if (s == null) { return null; } ArrayList resultList = new ArrayList(); if (s.length() < 2) { resultList.add(s); return resultList; } int length = s.length(); char currentChar; for (int i = 0; i < length; i++) { currentChar = s.charAt(i); String subString = s.substring(0, i) + s.substring(i + 1); ArrayList subPermutations = permutations(subString); for (String item : subPermutations) { resultList.add(currentChar + item); } } return resultList; } 

Estoy intentando implementar la misma función, pero devolver ArrayList y obtener int [] como parámetro. Estoy haciendo esto recursivamente como abajo:

 static ArrayList permutations(int[] arr) { ArrayList resultList = new ArrayList(); if (arr.length < 2) { resultList.add(arr); return resultList; } for (int i = 0; i < arr.length; i++) { int currentItem = arr[i]; int[] newArr = new int[arr.length - 1]; int[] newPermutation = new int[arr.length]; int j; // System.arraycopy(arr, 0, newArr, 0, i); // System.arraycopy(arr, i + 1, newArr, i, arr.length - i - 1); for (j = 0; j < i; j++) { newArr[j] = arr[j]; } for (j = i + 1; j < arr.length; j++) { newArr[j - 1] = arr[j]; } ArrayList subPermutations = permutations(newArr); newPermutation[0] = currentItem; // for (int i1 = 0; i1 < subPermutations.size(); i1++) { // for (j = 0; j < subPermutations.get(i1).length; j++) { // newPermutation[j + 1] = subPermutations.get(i1)[j]; // } // // resultList.add(newPermutation); // } for (int[] item : subPermutations) { for (j = 0; j < item.length; j++) { newPermutation[j + 1] = item[j]; } resultList.add(newPermutation); } // return resultList; } return resultList; } 

Al pasar arreglos de tamaño 0, 1 y 2 como parámetro, todo está bien. Para todo lo demás mayor que 2, obtengo el número correcto de permutaciones, pero se repiten. Aquí está el resultado para size == 3 y passing {1, 5, 4}:

 1 4 5 1 4 5 5 4 1 5 4 1 4 5 1 4 5 1 

Por favor, dame un consejo si encuentras estos problemas antes.

¡Gracias por adelantado!

 import java.util.ArrayList; import java.util.Arrays; public class Answer { static  String arrayToString( E[] arr ) { final StringBuffer str = new StringBuffer(); for ( E e : arr ) str.append( e.toString() ); return str.toString(); } static  ArrayList permutations(E[] arr) { final ArrayList resultList = new ArrayList(); final int l = arr.length; if ( l == 0 ) return resultList; if ( l == 1 ) { resultList.add( arr ); return resultList; } E[] subClone = Arrays.copyOf( arr, l - 1); System.arraycopy( arr, 1, subClone, 0, l - 1 ); for ( int i = 0; i < l; ++i ){ E e = arr[i]; if ( i > 0 ) subClone[i-1] = arr[0]; final ArrayList subPermutations = permutations( subClone ); for ( E[] sc : subPermutations ) { E[] clone = Arrays.copyOf( arr, l ); clone[0] = e; System.arraycopy( sc, 0, clone, 1, l - 1 ); resultList.add( clone ); } if ( i > 0 ) subClone[i-1] = e; } return resultList; } static ArrayList permutations(String arr) { final Character[] c = new Character[ arr.length() ]; for ( int i = 0; i < arr.length(); ++i ) c[i] = arr.charAt( i ); final ArrayList perms = permutations(c); final ArrayList resultList = new ArrayList( perms.size() ); for ( Character[] p : perms ) { resultList.add( arrayToString( p ) ); } return resultList; } public static void main(String[] args) { ArrayList str_perms = permutations( "abc" ); for ( String p : str_perms ) System.out.println( p ); ArrayList int_perms = permutations( new Integer[]{ 1, 2, 3, 4 } ); for ( Integer[] p : int_perms ) System.out.println( arrayToString( p ) ); } } 

Este código toma elementos de cadena, pero me puede modificar para que funcione con enteros:

 import java.util.*; /** * Write a description of class GeneratePermutations here. * * @author Kushtrim * @version 1.01 */ public class GeneratePermutations { public static void main(String args[]) { GeneratePermutations g = new GeneratePermutations(); String[] elements = {"a","b","c",}; ArrayList permutations = g.generatePermutations(elements); for ( String s : permutations) { System.out.println(s); } //System.out.println(permutations.get(999999)); } private ArrayList generatePermutations( String[] elements ) { ArrayList permutations = new ArrayList(); if ( elements.length == 2 ) { String x1 = elements[0] + elements[1]; String x2 = elements[1] + elements[0]; permutations.add(x1); permutations.add(x2); } else { for ( int i = 0 ; i < elements.length ; i++) { String[] elements2 = new String[elements.length -1]; int kalo = 0; for( int j =0 ; j< elements2.length ; j++ ) { if( i == j) { kalo = 1; } elements2[j] = elements[j+kalo]; } ArrayList k2 = generatePermutations(elements2); for( String x : k2 ) { String s = elements[i]+x; permutations.add(s); } } } return permutations; } } 

A continuación hay una clase que contiene una solución que usa generics. La API es un poco diferente de lo que especificó, pero es mucho más flexible. Lo más fácil de ver con ejemplos. Tenga en cuenta que las entradas probablemente tienen más restricciones de las que estoy comprobando aquí.

 public static final class Permutations { private Permutations() {} public static  List get(Class itemClass, T... itemsPool) { return get(itemsPool.length, itemClass, itemsPool); } public static  List get(int size, Class itemClass, T... itemsPool) { if (size < 1) { return new ArrayList(); } int itemsPoolCount = itemsPool.length; List permutations = new ArrayList(); for (int i = 0; i < Math.pow(itemsPoolCount, size); i++) { T[] permutation = (T[]) Array.newInstance(itemClass, size); for (int j = 0; j < size; j++) { // Pick the appropriate item from the item pool given j and i int itemPoolIndex = (int) Math.floor((double) (i % (int) Math.pow(itemsPoolCount, j + 1)) / (int) Math.pow(itemsPoolCount, j)); permutation[j] = itemsPool[itemPoolIndex]; } permutations.add(permutation); } return permutations; } } 

Ejemplo de uso

Llamando a Permutations.get(2, Integer.class, 1, 0, -1); devolverá la siguiente lista de matrices de enteros:

 [ 1, 1] [ 0, 1] [-1, 1] [ 1, 0] [ 0, 0] [-1, 0] [ 1, -1] [ 0, -1] [-1, -1] 

Llamando a Permutations.get(3, Integer.class, 1, 0, -1); devolverá la siguiente lista de matrices de enteros. Tenga en cuenta que este ejemplo es idéntico al primero, excepto por el primer argumento, que ahora es 3 :

 [ 1, 1, 1] [ 0, 1, 1] [-1, 1, 1] [ 1, 0, 1] [ 0, 0, 1] [-1, 0, 1] [ 1, -1, 1] [ 0, -1, 1] [-1, -1, 1] [ 1, 1, 0] [ 0, 1, 0] [-1, 1, 0] [ 1, 0, 0] [ 0, 0, 0] [-1, 0, 0] [ 1, -1, 0] [ 0, -1, 0] [-1, -1, 0] [ 1, 1, -1] [ 0, 1, -1] [-1, 1, -1] [ 1, 0, -1] [ 0, 0, -1] [-1, 0, -1] [ 1, -1, -1] [ 0, -1, -1] [-1, -1, -1] 

// ¡Aquí hay una versión recursiva que no fue difícil de comprometer con la memoria humana! O (n!) Permutaciones.

 public static Set getPermutationsRecursive(Integer[] num){ if (num == null) return null; Set perms = new HashSet<>(); //base case if (num.length == 0){ perms.add(new Integer[0]); return perms; } //shave off first int then get sub perms on remaining ints. //...then insert the first into each position of each sub perm..recurse int first = num[0]; Integer[] remainder = Arrays.copyOfRange(num,1,num.length); Set subPerms = getPermutationsRecursive(remainder); for (Integer[] subPerm: subPerms){ for (int i=0; i <= subPerm.length; ++i){ // '<=' IMPORTANT !!! Integer[] newPerm = Arrays.copyOf(subPerm, subPerm.length+1); for (int j=newPerm.length-1; j>i; --j) newPerm[j] = newPerm[j-1]; newPerm[i]=first; perms.add(newPerm); } } return perms; } 
 /** * * @param startIndex is the position of the suffix first element * @param prefix is the prefix of the pattern * @param suffix is the suffix of the pattern, will determine the complexity * permute method. * * * The block if (suffix.length == 1) will print * the only possible combination of suffix and return for computing next * combination. * * * The part after if (suffix.length == 1) is reached if suffix * length is not 1 that is there may be many possible combination of suffix * therefore make a newSuffix which will have suffix length * (suffix.length - 1) and recursively compute the possible * combination of this new suffix and also the original suffix prefix * positioned by startIndex will change by increasing its value * by one (startIndex + 1) % suffix.length * * * T(N) = N * T(N - 1) + N * = N! + N!(1 + 1/N + 1/(N * (N - 1)) + ... + 1/N!) * * */ public static void permute(int startIndex, int prefix[], int suffix[]) { if (suffix.length == 1) { for (int i = 0; i < prefix.length; i++) { System.out.print(prefix[i] + " "); } System.out.print(suffix[0]); System.out.println(" "); return; } for (int i = 0; i < suffix.length; i++) { counter++; int newPrefix[] = new int[prefix.length + 1]; System.arraycopy(prefix, 0, newPrefix, 0, prefix.length); newPrefix[prefix.length] = suffix[startIndex]; int newSuffix[] = new int[suffix.length - 1]; for (int j = 1; j < suffix.length; j++) { newSuffix[j - 1] = suffix[(startIndex + j) % suffix.length]; } permute((startIndex % newSuffix.length), newPrefix, newSuffix); startIndex = (startIndex + 1) % suffix.length; } } 

Escribí ese código hace un tiempo y lo edité un poco para que coincida con sus solicitudes. Espero que funcione.

 static ArrayList permutations(String s) { ArrayList ret = new ArrayList(); permutation(s.toCharArray(), 0, ret); return ret; } public static void permutation(char[] arr, int pos, ArrayList list){ if(arr.length - pos == 1) list.add(new String(arr)); else for(int i = pos; i < arr.length; i++){ swap(arr, pos, i); permutation(arr, pos+1, list); swap(arr, pos, i); } } public static void swap(char[] arr, int pos1, int pos2){ char h = arr[pos1]; arr[pos1] = arr[pos2]; arr[pos2] = h; } 

ACTUALIZAR
Lo probé en ideone.com . Parece funcionar. De nada. 🙂

ACTUALIZACIÓN 2
Básicamente debe ser el mismo código con matrices de int:

 static ArrayList permutations(int[] a) { ArrayList ret = new ArrayList(); permutation(a, 0, ret); return ret; } public static void permutation(int[] arr, int pos, ArrayList list){ if(arr.length - pos == 1) list.add(arr.clone()); else for(int i = pos; i < arr.length; i++){ swap(arr, pos, i); permutation(arr, pos+1, list); swap(arr, pos, i); } } public static void swap(int[] arr, int pos1, int pos2){ int h = arr[pos1]; arr[pos1] = arr[pos2]; arr[pos2] = h; } 

ACTUALIZACIÓN 3
Funciona con int también: http://ideone.com/jLpZow

Al agregar un TreeSet, elimina los duplicados y ordena las permutaciones.


 package permutations; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Scanner; import java.util.TreeSet; public class Permutations { public static void main(String args[]) { Scanner scanner = new Scanner(new InputStreamReader(System.in)); System.out.println("This application accepts input of a string and creates a list of all possible permutations\n\r"); System.out.println("Please Enter a string of characters"); String input = scanner.nextLine(); String[] elements = input.split(""); Permutations g = new Permutations(); ArrayList permutations = g.generatePermutations(elements); TreeSet ts = new TreeSet(); for ( String s : permutations) { //System.out.println(s); ts.add(s); } System.out.println("List of all possible permutations"); System.out.println(ts); } private ArrayList generatePermutations( String[] elements ) { ArrayList permutations = new ArrayList(); if ( elements.length == 2 ) { String x1 = elements[0] + elements[1]; String x2 = elements[1] + elements[0]; permutations.add(x1); permutations.add(x2); } else { for ( int i = 0 ; i < elements.length ; i++) { String[] elements2 = new String[elements.length -1]; int kalo = 0; for( int j =0 ; j< elements2.length ; j++ ) { if( i == j) { kalo = 1; } elements2[j] = elements[j+kalo]; } ArrayList k2 = generatePermutations(elements2); for( String x : k2 ) { String s = elements[i]+x; permutations.add(s); } } } return permutations; } } 

Aquí tienes, el código de ejemplo siguiente usa el método recursivo para obtener la permutación. Es genérico y puede especificar la ubicación de salida como lo desee. Una ventaja es que también puede especificar el delimitador.

 import java.io.FileNotFoundException; import java.io.OutputStream; import java.io.PrintStream; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Permutation { //The entry of the permutation method public static  List permute(T[] arr){ List result = new ArrayList(); permute(new ArrayList(), Arrays.asList(arr), result); return result; } //This is the actual method doing the permutation private static  void permute(List pre, List cur, List out){ int size = cur.size(); if(size == 0){ out.add((T[])pre.toArray()); } else { for(int i=0; i tmpPre = new ArrayList(pre); List tmpCur = new ArrayList(cur); tmpPre.add(cur.get(i)); tmpCur.remove((T)cur.get(i)); permute(tmpPre, tmpCur, out); } } } //Print each row of the permutated values private static  void print(List list, OutputStream out, char delim){ try{ for(T[] i : list){ int count = 0; for(T t : i){ if(++count == i.length){ out.write((t.toString()).getBytes()); } else{ out.write((t.toString()+delim).getBytes()); } } out.write("\n".getBytes()); } } catch (Exception ex){ ex.printStackTrace(); } } public static void main(String[] args) throws FileNotFoundException { Integer[] ints = new Integer[] {1, 2, 3, 4}; Permutation.print(Permutation.permute(ints), System.out, ','); Character[] chars = {'a', 'b', 'c', 'd', 'e'}; Permutation.print(Permutation.permute(chars), new PrintStream("permute.txt"), ' '); String[] strs = {"abc", "123"}; Permutation.print(Permutation.permute(strs), System.err, ' '); } } 

Aquí está mi solución ( esencia ):

 import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.function.Consumer; import java.util.stream.Collectors; import java.util.stream.IntStream; /** * @author Karol Krol */ public class Permutation { private Permutation() { } public static List> permutation(final int[] numbers) { final PermutationCollector permutationCollector = new PermutationCollector(); permutation(new int[0], numbers, permutationCollector); return permutationCollector.getResult(); } private static void permutation(int[] prefix, int[] array, final Consumer operation) { int length = array.length; if (length == 0) { operation.accept(prefix); } else { for (int i = 0; i < length; ++i) { final int[] newPrefix = append(prefix, array[i]); final int[] reducedArray = reduce(array, i); permutation(newPrefix, reducedArray, operation); } } } private static int[] append(int[] array, int element) { int newLength = array.length + 1; array = Arrays.copyOf(array, newLength); array[newLength - 1] = element; return array; } private static int[] reduce(int[] array, int index) { final int newLength = array.length - 1; if (index == 0) { return Arrays.copyOfRange(array, 1, array.length); } else { final int[] dest = new int[newLength]; System.arraycopy(array, 0, dest, 0, index); System.arraycopy(array, index + 1, dest, index, newLength - index); return dest; } } public static class PermutationCollector implements Consumer { private List> result = new ArrayList<>(); @Override public void accept(int[] ints) { result.add(IntStream.of(ints).boxed().collect(Collectors.toList())); } public List> getResult() { return result; } } }