Generando todas las permutaciones posibles de una lista recursivamente

Estoy tratando de generar recursivamente todos los elementos en una lista recursivamente. He visto algunas soluciones a preguntas similares a esto, pero no he podido hacer que mi código funcione. ¿Podría alguien señalar cómo puedo arreglar mi código?

Esto está abierto a todos los S / O’ers, no solo a personas de Java.

(También debo señalar que se bloquea con una excepción SO).

Entrada de muestra: [1, 2, 3]

Salida: [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

//allPossibleItems is an AL of all items //this is called with generatePerm(null, new ArrayList); private void generatePerm(Item i, ArrayList a) { if(i != null) { a.add(i); } if (a.size() == DESIRED_SIZE){ permutations.add(a); return; } for(int j = 0; j < allPossibleItems.size(); j ++) { if(allPossibleItems.get(j) != i) generatePerm(allPossibleItems.get(j), a); } } 

Si allPossibleItems contiene dos elementos diferentes, xey, escribe sucesivamente xey en la lista a hasta que llegue a DESIRED_SIZE. ¿Es eso lo que realmente quieres? Si elige DESIRED_SIZE lo suficientemente grande, tendrá demasiadas llamadas recursivas en la stack, de ahí la excepción SO.

Lo que haría (si el original no tiene dobles / duplicados):

  public  List> generatePerm(List original) { if (original.size() == 0) { List> result = new ArrayList>(); result.add(new ArrayList()); return result; } E firstElement = original.remove(0); List> returnValue = new ArrayList>(); List> permutations = generatePerm(original); for (List smallerPermutated : permutations) { for (int index=0; index <= smallerPermutated.size(); index++) { List temp = new ArrayList(smallerPermutated); temp.add(index, firstElement); returnValue.add(temp); } } return returnValue; } 

El problema es que debe clonar ArrayList antes de hacer la llamada recursiva. De lo contrario, agregará siempre a la misma ArrayList.

 //allPossibleItems is an AL of all items //this is called with generatePerm(null, new ArrayList); private void generatePerm(Item i, ArrayList a) { if(i != null) { a.add(i); } if (a.size() == DESIRED_SIZE){ permutations.add(a); return; } for(int j = 0; j < allPossibleItems.size(); j ++) { if(!a.contains(allPossibleItems.get(j))){ ArrayList b = clone(a); generatePerm(allPossibleItems.get(j), b); } } } 
 private List generatePerm(List a, int depth) { // this is the method definition you want // to generate all permutations, you need cycle thru all elements in your list and for each element // add that element to each member of generatePerm(a, depth - 1); // if you want combinations, you need to remove the element and then call /// generateCombinations with the remaining list } 

Google me lleva a esta pregunta. encontré el siguiente método más rápido que otros métodos.

Básicamente utilizo un Set para generar recursivamente las permutaciones. Para ilustrar, la primera posición puede contener todos los valores posibles, la segunda todos los valores posibles excepto el primer valor, y así sucesivamente. Cuando llegamos a la última posición, solo hay una posibilidad.

En términos de parámetros para la función recursiva, (1) transmitimos lo que ya se ha registrado como stream de stream. (2) Pasamos el Arraylist que contiene los resultados – list_of_permutes (3) Pasamos un conjunto desde el cual elegir el número actual – currentnums. En el último nivel, tenemos una permutación completa, que luego se agrega a la lista de arrays – list_of_permutes y esto se devuelve hacia arriba.

 public static ArrayList recurse_nums(Set currentnums, String currentstring, ArrayList list_of_permutes){ if(currentnums.size()==1){ int elem = currentnums.iterator().next(); list_of_permutes.add(currentstring + Integer.toString(elem)); return list_of_permutes; } for(int a:currentnums){ String newstring = currentstring + a; Set newnums = new HashSet<>(); newnums.addAll(currentnums); newnums.remove(a); recurse_nums(newnums, newstring,list_of_permutes); } return list_of_permutes; } 

Esto se puede llamar de algo como lo siguiente:

 public static ArrayList permute_array(int[] arr){ Set currentnums = new HashSet<>(); for (int i = 0; i < arr.length; i++) {currentnums.add(arr[i]);} ArrayList permutations = new ArrayList(); recurse_nums(currentnums,"",permutations); return permutations; }