Prodotto cartesiano di insiemi arbitrari in Java

Question

Conosci alcune librerie Java interessanti che ti consentono di creare un prodotto cartesiano di due (o più) insiemi?

Per esempio:Ne ho tre set.Uno con oggetti della classe Person, il secondo con oggetti della classe Gift e il terzo con oggetti della classe GiftExtension.

Voglio generare un set contenente tutte le possibili triple Person-Gift-GiftExtension.

Il numero di set potrebbe variare, quindi non posso farlo nel ciclo foreach annidato.In alcune condizioni la mia domanda deve creare un prodotto della coppia Persona-Gift, a volte è tripla Persona-Gift-GiftExtension, a volte potrebbero anche esserci set Persona-Gift-GiftExtension-GiftSecondExtension-GiftThirdExtension, ecc.

Answer 1

Modifica: soluzioni precedenti per due set rimossi. Vedere cronologia per i dettagli.

Ecco un modo per farlo in modo ricorsivo per un numero arbitrario di insiemi:

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;
}

Si noti che è impossibile mantenere tutte le informazioni di tipo generico con i set restituiti. Se si sapeva in anticipo come molti set si voleva prendere il prodotto di, è possibile definire una tupla generico per ritenere che molti elementi (ad esempio Triple<A, B, C>), ma non c'è modo di avere un numero arbitrario di parametri generici in Java.

Answer 2

Questa è una domanda piuttosto vecchio, ma perché non utilizzare di Guava prodotto cartesiano ?

Answer 3

Il metodo di seguito crea il prodotto cartesiano di una lista di lista di stringhe:

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;
}

Esempio:

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

produrrebbe questo:

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

Answer 4

  

Il numero di serie può variare in modo da   non si può fare questo in ciclo foreach nidificato.

Due suggerimenti:

• A x B x C = A x (B x C)
• ricorsione

Answer 5

soluzioni basati su indici

Lavorare con gli indici è un'alternativa che è veloce e la memoria efficiente e può gestire qualsiasi numero di gruppi. Implementazione Iterable permette un facile utilizzo in un per-ogni ciclo. Vedere il metodo #main per un esempio di utilizzo.

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]]);
        }
    }
}

Answer 6

Ecco un Iterable, che permette di utilizzare un semplificata per-ciclo:

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 (")");
    }
}

Come si fa? Abbiamo bisogno di un Iterable, di utilizzare la semplificato per-loop, e un iteratore deve essere restituito dal Iterable. Torniamo un elenco di oggetti - questo potrebbe essere un set al posto di Lista, ma insieme non ha accesso indicizzato, quindi sarebbe un po 'più complicato, per la sua attuazione con l'insieme, invece di Lista. Invece di una soluzione generica, oggetto sarebbe stato bene per vari scopi, ma generici consentire una più restrizioni.

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;
            }
        }
    }
}

Il lavoro matematica è fatto nel 'metodo get'. Pensate a 2 serie di 10 elementi. Si dispone di un totale di 100 combinazioni, enumerati da 00, 01, 02, 10 ..., ... a 99. Per 5 X 10 elementi 50, per 2 x 3 elementi 6 combinazioni. Il modulo della dimensione sottolista aiuta a scegliere un elemento per ogni iterazione.

Iterable i la cosa meno interessante:

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);
    }
}

Per implementare Iterable, che permette la for-each tipo di ciclo, dobbiamo attuare iterator (), e per Iterator dobbiamo attuare hasNext (), next () e rimuovere ().

Risultato:

(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 7

Ecco una Iterator che conferisce al prodotto cartesiano di una matrice bidimensionale, in cui i componenti array rappresentano i set dalla domanda (si può sempre convertire Sets effettivi agli array):

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;
    }
}

L'idea di base è quella di trattare count come un numero multi-radix (i cifre ha la sua radice che è uguale alla lunghezza del i'th "set"). Ogni volta che abbiamo per risolvere next (cioè, quando viene chiamato e hasNext() next è null), scomponiamo il numero nelle sue cifre in questo multi-radix. Queste cifre vengono ora utilizzati come indici da cui attingiamo elementi dai diversi insiemi.

uso Esempio:

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));
}

Output:

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

Se uno non piace gli array, il codice è banalmente convertibile in utilizzando collezioni.

Credo che questo è più o meno simile alla risposta data dal "utente sconosciuto", solo senza ricorsione e collezioni.

Answer 8

Sì, c'è Java funzionale .

Per un set (s):

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

Answer 9

L'impronta di memoria (e di elaborazione) necessaria per un prodotto cartesiano può sfuggire di mano abbastanza rapidamente.L'implementazione ingenua può esaurire la memoria e richiedere molto tempo.Sarebbe bello conoscere le operazioni che si intende eseguire in tale insieme, in modo da suggerire una strategia di implementazione.

In ogni caso, fai qualcosa come Sets.SetView sulle raccolte Google.Questo è un set che viene supportato da altri set man mano che vengono aggiunti.L'idea per loro il problema è evitare la chiamata addAll.L'idea per tuo il problema è evitare di aggiungere NxMxK ​​a un set.

Le raccolte Google possono essere trovate qui e la classe menzionata lo è Qui

Answer 10

Come sull'utilizzo odl.com.google.common18.collect.Sets e chiamando Sets.cartesianProduct () Metodo