Producto cartesiano de conjuntos arbitrarios en Java

cartesian-product

Question

¿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 anidado. 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.

Answer 1

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

Dos consejos:

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

Answer 2

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<T> implements Iterator<T[]> {
    private final T[][] sets;
    private final IntFunction<T[]> arrayConstructor;

    private int count = 0;
    private T[] next = null;

    public CartesianIterator(T[][] sets, IntFunction<T[]> arrayConstructor) {
        Objects.requireNonNull(sets);
        Objects.requireNonNull(arrayConstructor);

        this.sets = copySets(sets);
        this.arrayConstructor = arrayConstructor;
    }

    private static <T> 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<String[]> 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.

Answer 3

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 <Object> lc = Arrays.asList (new Object [] {''A'', ''B'', ''C'', ''D''});
        List <Object> lC = Arrays.asList (new Object [] {''a'', ''b'', ''c''});   
        List <Object> li = Arrays.asList (new Object [] {1, 2, 3, 4});
            // sometimes, a generic solution like List <List <String>>
            // might be possible to use - typically, a mixture of types is 
            // the common nominator 
        List <List <Object>> llo = new ArrayList <List <Object>> ();
        llo.add (lc);
        llo.add (lC);
        llo.add (li);

        // Preparing the List of Lists is some work, but then ...    
        CartesianIterable <Object> ci = new CartesianIterable <Object> (llo);

        for (List <Object> lo: ci)
            show (lo);
    }

    public static void show (List <Object> 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 genéricos permiten más restricciones.

class CartesianIterator <T> implements Iterator <List <T>> {

    private final List <List <T>> lilio;    
    private int current = 0;
    private final long last;

    public CartesianIterator (final List <List <T>> llo) {
        lilio = llo;
        long product = 1L;
        for (List <T> lio: lilio)
            product *= lio.size ();
        last = product;
    } 

    public boolean hasNext () {
        return current != last;
    }

    public List <T> next () {
        ++current;
        return get (current - 1, lilio);
    }

    public void remove () {
        ++current;
    }

    private List<T> get (final int n, final List <List <T>> lili) {
        switch (lili.size ())
        {
            case 0: return new ArrayList <T> (); // no break past return;
            default: {
                List <T> inner = lili.get (0);
                List <T> lo = new ArrayList <T> ();
                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 <T> implements Iterable <List <T>> {

    private List <List <T>> lilio;  

    public CartesianIterable (List <List <T>> llo) {
        lilio = llo;
    }

    public Iterator <List <T>> iterator () {
        return new CartesianIterator <T> (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, )

Answer 4

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

protected <T> List<List<T>> cartesianProduct(List<List<T>> lists) {
    List<List<T>> resultLists = new ArrayList<List<T>>();
    if (lists.size() == 0) {
        resultLists.add(new ArrayList<T>());
        return resultLists;
    } else {
        List<T> firstList = lists.get(0);
        List<List<T>> remainingLists = cartesianProduct(lists.subList(1, lists.size()));
        for (T condition : firstList) {
            for (List<T> remainingList : remainingLists) {
                ArrayList<T> resultList = new ArrayList<T>();
                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]]

Answer 5

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

Answer 6

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á here

Answer 7

Sí, hay Java funcional .

Para un conjunto (s):

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

Answer 8

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<Set<Object>> 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<Set<Object>> _cartesianProduct(int index, Set<?>... sets) {
    Set<Set<Object>> ret = new HashSet<Set<Object>>();
    if (index == sets.length) {
        ret.add(new HashSet<Object>());
    } else {
        for (Object obj : sets[index]) {
            for (Set<Object> 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<A, B, C> ), pero no hay forma de tener un número arbitrario de parámetros genéricos en Java.

Answer 9

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<int[]>, Iterator<int[]> {

    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<int[]> iterator() {
        return this;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
     * Usage example. Prints out
     * 
     * <pre>
     * [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
     * ...
     * </pre>
     */
    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]]);
        }
    }
}