Producto cartesiano de conjuntos arbitrarios en Java

¿Conoces algunas librerías ordenadas de Java que te permiten hacer productos cartesianos de dos (o más) conjuntos?

Por ejemplo: tengo tres juegos. Uno con objetos de clase Persona, segundo con objetos de clase Regalo y tercero con objetos de clase GiftExtension.

Quiero generar un conjunto que contenga todos los triples posibles Person-Gift-GiftExtension.

La cantidad de conjuntos puede variar, así que no puedo hacer esto en un ciclo foreach nested. Bajo ciertas condiciones, mi aplicación necesita hacer un producto de pareja Person-Gift, a veces es triple Person-Gift-GiftExtension, a veces puede haber sets de Person-Gift-GiftExtension-GiftSecondExtension-GiftThirdExtension, etc.

Editar: soluciones anteriores para dos conjuntos eliminados. Ver el historial de edición para más detalles.

Aquí hay una manera de hacerlo recursivamente para un número arbitrario de conjuntos:

public static Set> cartesianProduct(Set... sets) { if (sets.length < 2) throw new IllegalArgumentException( "Can't have a product of fewer than two sets (got " + sets.length + ")"); return _cartesianProduct(0, sets); } private static Set> _cartesianProduct(int index, Set... sets) { Set> ret = new HashSet>(); if (index == sets.length) { ret.add(new HashSet()); } else { for (Object obj : sets[index]) { for (Set set : _cartesianProduct(index+1, sets)) { set.add(obj); ret.add(set); } } } return ret; } 

Tenga en cuenta que es imposible mantener cualquier tipo de información genérica con los conjuntos devueltos. Si supiera con anticipación de cuántos conjuntos quería tomar el producto, podría definir una tupla genérica para contener tantos elementos (por ejemplo Triple ), pero no hay forma de tener un número arbitrario de parámetros generics en Java.

Esta es una pregunta muy antigua, pero ¿por qué no utilizar el producto cartesiano de Guava ?

El siguiente método crea el producto cartesiano de una lista de cadenas de caracteres:

 protected  List> cartesianProduct(List> lists) { List> resultLists = new ArrayList>(); if (lists.size() == 0) { resultLists.add(new ArrayList()); return resultLists; } else { List firstList = lists.get(0); List> remainingLists = cartesianProduct(lists.subList(1, lists.size())); for (T condition : firstList) { for (List remainingList : remainingLists) { ArrayList resultList = new ArrayList(); resultList.add(condition); resultList.addAll(remainingList); resultLists.add(resultList); } } } return resultLists; } 

Ejemplo:

 System.out.println(cartesianProduct(Arrays.asList(Arrays.asList("Apple", "Banana"), Arrays.asList("Red", "Green", "Blue")))); 

cedería esto:

 [[Apple, Red], [Apple, Green], [Apple, Blue], [Banana, Red], [Banana, Green], [Banana, Blue]] 

La cantidad de conjuntos puede variar, así que no puedo hacer esto en un ciclo foreach nested.

Dos consejos:

  • A x B x C = A x (B x C)
  • Recursión

Solución basada en índices

Trabajar con los índices es una alternativa que es rápida y eficiente en la memoria y puede manejar cualquier cantidad de conjuntos. La implementación de Iterable permite un uso sencillo en un bucle for-each. Vea el método #main para un ejemplo de uso.

 public class CartesianProduct implements Iterable, Iterator { private final int[] _lengths; private final int[] _indices; private boolean _hasNext = true; public CartesianProduct(int[] lengths) { _lengths = lengths; _indices = new int[lengths.length]; } public boolean hasNext() { return _hasNext; } public int[] next() { int[] result = Arrays.copyOf(_indices, _indices.length); for (int i = _indices.length - 1; i >= 0; i--) { if (_indices[i] == _lengths[i] - 1) { _indices[i] = 0; if (i == 0) { _hasNext = false; } } else { _indices[i]++; break; } } return result; } public Iterator iterator() { return this; } public void remove() { throw new UnsupportedOperationException(); } /** * Usage example. Prints out * * 
 * [0, 0, 0] a, NANOSECONDS, 1 * [0, 0, 1] a, NANOSECONDS, 2 * [0, 0, 2] a, NANOSECONDS, 3 * [0, 0, 3] a, NANOSECONDS, 4 * [0, 1, 0] a, MICROSECONDS, 1 * [0, 1, 1] a, MICROSECONDS, 2 * [0, 1, 2] a, MICROSECONDS, 3 * [0, 1, 3] a, MICROSECONDS, 4 * [0, 2, 0] a, MILLISECONDS, 1 * [0, 2, 1] a, MILLISECONDS, 2 * [0, 2, 2] a, MILLISECONDS, 3 * [0, 2, 3] a, MILLISECONDS, 4 * [0, 3, 0] a, SECONDS, 1 * [0, 3, 1] a, SECONDS, 2 * [0, 3, 2] a, SECONDS, 3 * [0, 3, 3] a, SECONDS, 4 * [0, 4, 0] a, MINUTES, 1 * [0, 4, 1] a, MINUTES, 2 * ... * 

*/ public static void main(String[] args) { String[] list1 = { "a", "b", "c", }; TimeUnit[] list2 = TimeUnit.values(); int[] list3 = new int[] { 1, 2, 3, 4 }; int[] lengths = new int[] { list1.length, list2.length, list3.length }; for (int[] indices : new CartesianProduct(lengths)) { System.out.println(Arrays.toString(indices) // + " " + list1[indices[0]] // + ", " + list2[indices[1]] // + ", " + list3[indices[2]]); } } }

Aquí hay un Iterable, que le permite usar un for-loop simplificado:

 import java.util.*; // let's begin with the demo. Instead of Person and Gift, // I use the well known char and int. class CartesianIteratorTest { public static void main (String[] args) { List  lc = Arrays.asList (new Object [] {'A', 'B', 'C', 'D'}); List  lC = Arrays.asList (new Object [] {'a', 'b', 'c'}); List  li = Arrays.asList (new Object [] {1, 2, 3, 4}); // sometimes, a generic solution like List > // might be possible to use - typically, a mixture of types is // the common nominator List > llo = new ArrayList > (); llo.add (lc); llo.add (lC); llo.add (li); // Preparing the List of Lists is some work, but then ... CartesianIterable  ci = new CartesianIterable  (llo); for (List  lo: ci) show (lo); } public static void show (List  lo) { System.out.print ("("); for (Object o: lo) System.out.print (o + ", "); System.out.println (")"); } } 

¿Cómo se hace? Necesitamos un Iterable, para usar el for-loop simplificado, y un Iterator debe ser devuelto desde Iterable. Devolvemos una Lista de objetos: podría ser un conjunto en lugar de una lista, pero Set no tiene acceso indexado, por lo que sería un poco más complicado implementarlo con Set en lugar de List. En lugar de una solución genérica, Object habría estado bien para muchos propósitos, pero los generics permiten más restricciones.

 class CartesianIterator  implements Iterator > { private final List > lilio; private int current = 0; private final long last; public CartesianIterator (final List > llo) { lilio = llo; long product = 1L; for (List  lio: lilio) product *= lio.size (); last = product; } public boolean hasNext () { return current != last; } public List  next () { ++current; return get (current - 1, lilio); } public void remove () { ++current; } private List get (final int n, final List > lili) { switch (lili.size ()) { case 0: return new ArrayList  (); // no break past return; default: { List  inner = lili.get (0); List  lo = new ArrayList  (); lo.add (inner.get (n % inner.size ())); lo.addAll (get (n / inner.size (), lili.subList (1, lili.size ()))); return lo; } } } } 

El trabajo matemático se realiza en el método ‘get’. Piensa en 2 conjuntos de 10 elementos. Tienes un total de 100 combinaciones, enumeradas entre 00, 01, 02, … 10, … a 99. Para 5 X 10 elementos 50, para 2 X 3 elementos 6 combinaciones. El módulo del tamaño de la sublista ayuda a elegir un elemento para cada iteración.

Iterable es lo menos interesante aquí:

 class CartesianIterable  implements Iterable > { private List > lilio; public CartesianIterable (List > llo) { lilio = llo; } public Iterator > iterator () { return new CartesianIterator  (lilio); } } 

Para implementar Iterable, que permite el tipo para cada ciclo, tenemos que implementar iterator (), y para Iterator tenemos que implementar hasNext (), next () y remove ().

Resultado:

 (A, a, 1, ) (B, a, 1, ) (C, a, 1, ) (D, a, 1, ) (A, b, 1, ) (B, b, 1, ) (C, b, 1, ) (D, b, 1, ) ... (A, a, 2, ) ... (C, c, 4, ) (D, c, 4, ) 

Sí, hay Java funcional .

Para un conjunto (s):

s.bind (P.p2 (), s);

La huella de memoria (y procesamiento) necesaria para un producto cartesiano puede irse de las manos rápidamente. La implementación ingenua puede agotar la memoria y tomar mucho tiempo. Sería bueno saber las operaciones que planea realizar en dicho conjunto, para sugerir una estrategia de implementación.

En cualquier caso, haga algo así como Sets.SetView en las colecciones de google. Este es un conjunto respaldado por otros conjuntos a medida que se agregan. La idea de su problema es evitar la llamada addAll. La idea de su problema es evitar que NxMxK ​​se agregue a un conjunto.

Las colecciones de Google se pueden encontrar aquí y la clase mencionada está aquí

Aquí hay un Iterator que proporciona el producto cartesiano de una matriz bidimensional, donde los componentes de las matrices representan los conjuntos de la pregunta (uno siempre puede convertir Set reales en matrices):

 public class CartesianIterator implements Iterator { private final T[][] sets; private final IntFunction arrayConstructor; private int count = 0; private T[] next = null; public CartesianIterator(T[][] sets, IntFunction arrayConstructor) { Objects.requireNonNull(sets); Objects.requireNonNull(arrayConstructor); this.sets = copySets(sets); this.arrayConstructor = arrayConstructor; } private static  T[][] copySets(T[][] sets) { // If any of the arrays are empty, then the entire iterator is empty. // This prevents division by zero in `hasNext`. for (T[] set : sets) { if (set.length == 0) { return Arrays.copyOf(sets, 0); } } return sets.clone(); } @Override public boolean hasNext() { if (next != null) { return true; } int tmp = count; T[] value = arrayConstructor.apply(sets.length); for (int i = 0; i < value.length; i++) { T[] set = sets[i]; int radix = set.length; int index = tmp % radix; value[i] = set[index]; tmp /= radix; } if (tmp != 0) { // Overflow. return false; } next = value; count++; return true; } @Override public T[] next() { if (!hasNext()) { throw new NoSuchElementException(); } T[] tmp = next; next = null; return tmp; } } 

La idea básica es tratar el count como un número de múltiples radios (el dígito i tiene su propia raíz, que es igual a la longitud del conjunto i 'th "). Siempre que tengamos que resolver el next (es decir, cuando se llama hasNext() y next null ), descomponemos el número en sus dígitos en este multi-radix. Estos dígitos ahora se usan como los índices de los cuales extraemos elementos de los diferentes conjuntos.

Ejemplo de uso:

 String[] a = { "a", "b", "c"}; String[] b = { "X" }; String[] c = { "r", "s" }; String[][] abc = { a, b, c }; Iterable it = () -> new CartesianIterator<>(abc, String[]::new); for (String[] s : it) { System.out.println(Arrays.toString(s)); } 

Salida:

 [a, X, r] [b, X, r] [c, X, r] [a, X, s] [b, X, s] [c, X, s] 

Si a uno no le gustan las matrices, el código es trivialmente convertible en el uso de colecciones.

Supongo que esto es más o menos similar a la respuesta dada por "usuario desconocido", solo que sin recursividad y colecciones.