¿Cómo crear productos cartesianos sobre grupos arbitrarios de números en Java?

Question

Digamos que tengo 2 grupos de números:

{1, 2, 3}, 
{4, 5} 

Me gustaría crear un algoritmo (en Java) que da salida a los siguientes 6 combinaciones:

1,4 
1,5 
2,4 
2,5 
3,4 
3,5 

No puede haber un número arbitrario de grupos y un número arbitrario de miembros dentro de cada grupo. Entonces, en el ejemplo anterior, hay 2 grupos, el primer grupo tiene 3 miembros y el segundo grupo tiene 2 miembros. Otro ejemplo es el siguiente (3 grupos, 3 miembros en primeros grupos y 2 miembros en los grupos segundo y tercero):

{1, 2, 3}, 
{4, 5}, 
{6, 7} 

lo cual produciría los siguientes 12 combinaciones:

1,4,6 
1,4,7 
1,5,6 
1,5,7 

2,4,6 
2,4,7 
2,5,6 
2,5,7 

3,4,6 
3,4,7 
3,5,6 
3,5,7 

¿Cómo puedo hacer esto en Java? Estoy tratando de usar la recursividad y ya he visto un similar question, pero todavía me estoy quedando corto. ¡Gracias por la ayuda! (P.S. esto no es para una tarea)

Answer 1

dieron un poco aburrido y decidió darle una oportunidad. En caso de ser exactamente lo que necesita:

public static void main(String args[]) { 

    ArrayList<int[]> input = new ArrayList<int[]>(); 
    input.add(new int[] { 1, 2, 3 }); 
    input.add(new int[] { 4, 5 }); 
    input.add(new int[] { 6, 7 }); 

    combine(input, new int[input.size()], 0); 
} 

private static void combine(ArrayList<int[]> input, int[] current, int k) { 

    if(k == input.size()) { 
     for(int i = 0; i < k; i++) { 
      System.out.print(current[i] + " "); 
     } 
     System.out.println(); 
    } else {    
     for(int j = 0; j < input.get(k).length; j++) { 
      current[k] = input.get(k)[j]; 
      combine(input, current, k + 1); 
     }  
    } 
} 

Answer 2

Un posible enfoque (no necesariamente el más eficiente) podría ser adoptar un enfoque de dividir y conquistar. Es relativamente simple encontrar todas las permutaciones de dos grupos (la forma más tonta se anida para los bucles). Digamos que escribes una función llamada permute y hace permute(A,B) donde A (ej. {(1), (2), (3)}) y B (ej. {(4), (5)} son grupos de números y regresa usted todas las permutaciones de A & B como un solo grupo (por ejemplo, {(1,4), (1,5), (2,4), (2,5), (3,4), (3,5) }).

Así que cuando tiene N grupos en lugar de 2, lo más fácil es simplemente eliminar pequeñas porciones del problema. Digamos que tiene grupos A, B y C. En lugar de preocuparse por todos ellos por separado , se puede pensar que es algo así como:

permute(permute(A,B),C)

Buscar todas las permutaciones de A y B primero. Una vez que tenga ese resultado, encontrar todas las permutaciones de ese resultado con C. Y cuatro grupos A, B, C, D podría ser:

permute(permute(permute(A,B),C),D)

Y así sucesivamente. En cada paso del camino, toma el resultado de la permutación actual y lo permute con el siguiente grupo en la lista de grupos que obtuvo como entrada. Solo está combinando dos grupos a la vez, por lo que el algoritmo no tiene que cambiar según la cantidad de grupos que obtenga como entrada.

Cuando estás haciendo recursividad, hay algunas preguntas importantes que debe responder:

1. ¿Se puede romper de forma recursiva el problema en problemas más pequeños y que tienen solución? Creo que los ejemplos anteriores prueban que puedes.

2. ¿Cuál es el caso base? ¿Cuál es la solución que hará que la recursión se detenga y se relaje? Por lo general, debe ser algo realmente simple para que su recursión pueda funcionar hacia abajo. En este caso, probablemente se trata de algo como permute(A,{}) donde {} es el conjunto vacío.

3. ¿Cuál es el caso recursivo?¿Cómo dividirás una porción del problema y recurrirás en un subconjunto más pequeño del problema? Creo que la explicación inicial te da una forma de hacer esto. Solo divide un grupo a la vez y permítelo con tu resultado en constante crecimiento.

Sin duda existen otras soluciones para este problema, esta es solo la primera que se me vino a la cabeza. A medida que N se hace cada vez más grande, este algoritmo será extremadamente lento, ya que no es muy eficiente.

Así que incluso si no usas esta solución, ¡espero que te lleve por el buen camino!

Answer 3

¿Qué hay de la siguiente pseudo código (w/o recursividad)

// Create the initial result filled with the first set of numbers 
List result = new List() 
For each number in the first set 
    result.add(new List(number)) 

// Iterate over the following sets to permutate over 
For each remaining set S 
    List newResult = new List() 
    For each list L in result 
    For each number N in S 
     newResult.add(copy of L with N added) 
    result = newResult 

Answer 4

Si puede utilizar las bibliotecas, Guava'sSets.cartesianProduct(List<Set<E>>) hace exactamente lo que estás buscando. (Divulgación: contribuyo con la guayaba).