Esta es el arreglo más exacta que encomtrarás compartir, pero mírala detenidamente y analiza si se adapta a tu proyecto.
Solución:
Prueba algo como esto:
public static void generate(int[][] sets)
int solutions = 1;
for(int i = 0; i < sets.length; solutions *= sets[i].length, i++);
for(int i = 0; i < solutions; i++)
int j = 1;
for(int[] set : sets)
System.out.print(set[(i/j)%set.length] + " ");
j *= set.length;
System.out.println();
public static void main(String[] args)
generate(new int[][]1,2,3, 3,2, 5,6,7);
que imprimirá:
1 3 5
2 3 5
3 3 5
1 2 5
2 2 5
3 2 5
1 3 6
2 3 6
3 3 6
1 2 6
2 2 6
3 2 6
1 3 7
2 3 7
3 3 7
1 2 7
2 2 7
3 2 7
Implementé el algoritmo anterior basado en (creo) uno de los libros TAOCP de Knuth (en los comentarios @chikitin tiene una referencia más específica: está en PRE FASCICLE 2A sección 7.2.1.1 Generación de todo n-tupla, de The Art Of Programación informática de Knuth, Addison Wesley).
Tenga en cuenta que he nombrado las matrices set, pero no es necesario que contengan elementos únicos, por supuesto. La vez que lo usé, contenían elementos únicos, de ahí el nombre.
EDITAR
Es prácticamente una traducción 1 a 1:
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Vector;
public class Foo
private LinkedHashMap> dataStructure;
public Foo(LinkedHashMap> dataStructure)
this.dataStructure = dataStructure;
public String[][] allUniqueCombinations()
int n = dataStructure.keySet().size();
int solutions = 1;
for(Vector vector : dataStructure.values())
solutions *= vector.size();
String[][] allCombinations = new String[solutions + 1][];
allCombinations[0] = dataStructure.keySet().toArray(new String[n]);
for(int i = 0; i < solutions; i++)
Vector combination = new Vector(n);
int j = 1;
for(Vector vec : dataStructure.values())
combination.add(vec.get((i/j)%vec.size()));
j *= vec.size();
allCombinations[i + 1] = combination.toArray(new String[n]);
return allCombinations;
public static void main(String[] args)
LinkedHashMap> data = new LinkedHashMap>();
data.put("foo", new Vector(Arrays.asList("1", "2", "3")));
data.put("bar", new Vector(Arrays.asList("3", "2")));
data.put("baz", new Vector(Arrays.asList("5", "6", "7")));
Foo foo = new Foo(data);
for(String[] combination : foo.allUniqueCombinations())
System.out.println(Arrays.toString(combination));
Si ejecuta la clase anterior, se imprime lo siguiente:
[foo, bar, baz]
[1, 3, 5]
[2, 3, 5]
[3, 3, 5]
[1, 2, 5]
[2, 2, 5]
[3, 2, 5]
[1, 3, 6]
[2, 3, 6]
[3, 3, 6]
[1, 2, 6]
[2, 2, 6]
[3, 2, 6]
[1, 3, 7]
[2, 3, 7]
[3, 3, 7]
[1, 2, 7]
[2, 2, 7]
[3, 2, 7]
¿Qué tal generar el producto de forma perezosa, es decir. ¿Solo crea la tupla cuando accede a ella?
/**
* A random access view of tuples of a cartesian product of ArrayLists
*
* Orders tuples in the natural order of the cartesian product
*
* @param T the type for both the values and the stored tuples, ie. values of the cartesian factors are singletons
* While the type of input sets is List with elements being treated as singletons
*
*/
abstract public class CartesianProductView extends AbstractList
private final List> factors;
private final int size;
/**
* @param factors the length of the factors (ie. the elements of the factors argument) should not change,
* otherwise get may not return all tuples, or throw exceptions when trying to access the factors outside of range
*/
public CartesianProductView(List> factors)
this.factors = new ArrayList<>(factors);
Collections.reverse(this.factors);
int acc = 1;
for (Iterator> iter = this.factors.iterator(); iter.hasNext(); )
acc *= iter.next().size();
this.size = acc;
@Override
public T get(int index)
@Override
public int size()
return size;
private T makeTupleOrSingleton(T left, T right)
if (right == null)
return left;
return makeTuple(left, right);
/**
*
* @param left a singleton of a value
* @param right a tuple of values taken from the cartesian product factors, with null representing the empty set
* @return the sum of left and right, with the value of left being put in front
*/
abstract protected T makeTuple(T left, T right);
y úsalo así
final List> l1 = new ArrayList>() add(singletonList("a")); add(singletonList("b")); add(singletonList("c")); ;
final List> l2 = new ArrayList>() add(singletonList("X")); add(singletonList("Y")); ;
final List> l3 = new ArrayList>() add(singletonList("1")); add(singletonList("2")); add(singletonList("3")); add(singletonList("4")); ;
List>> in = new ArrayList>>() add(l1); add(l2); add(l3); ;
List> a = new CartesianProductView>(in)
@Override
protected List makeTuple(final List left, final List right)
return new ArrayList() add(left.get(0)); addAll(right); ;
;
System.out.println(a);
El resultado:
[[a, X, 1], [a, X, 2], [a, X, 3], [a, X, 4], [a, Y, 1], [a, Y, 2], [a, Y, 3], [a, Y, 4], [b, X, 1], [b, X, 2], [b, X, 3], [b, X, 4], [b, Y, 1], [b, Y, 2], [b, Y, 3], [b, Y, 4], [c, X, 1], [c, X, 2], [c, X, 3], [c, X, 4], [c, Y, 1], [c, Y, 2], [c, Y, 3], [c, Y, 4]]
Como una ventaja adicional, puede usarlo para unir cadenas con todos:
final List l1 = new ArrayList() add("a"); add("b"); add("c"); ;
final List l2 = new ArrayList() add("X"); add("Y"); ;
final List l3 = new ArrayList() add("1"); add("2"); add("3"); add("4"); ;
List> in = new ArrayList>() add(l1); add(l2); add(l3); ;
List a = new CartesianProductView(in)
@Override
protected String makeTuple(String left, String right)
return String.format("%s%s", left, right);
;
System.out.println(a);
El resultado:
[aX1, aX2, aX3, aX4, aY1, aY2, aY3, aY4, bX1, bX2, bX3, bX4, bY1, bY2, bY3, bY4, cX1, cX2, cX3, cX4, cY1, cY2, cY3, cY4]
Guava tiene un método de utilidad que devuelve un producto cartesiano de la lista de conjuntos dada: Sets.cartesianProduct.
Sección de Reseñas y Valoraciones
Si te ha resultado provechoso este post, sería de mucha ayuda si lo compartieras con otros programadores y nos ayudes a difundir nuestro contenido.
¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)