Produit cartésien d'ensembles arbitraires en Java

C'est une très vieille question, mais pourquoi ne pas utiliser goyava's cartesianProduct?

la méthode ci-dessous crée le produit cartésien d'une liste de chaînes:

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

Exemple:

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

donnerait ceci:

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

le nombre de jeux peut varier donc I ne peut pas faire cela dans la boucle de foreach imbriquée.

deux indices:

• A x B x C = A x (B x c)
• la Récursivité

Solution indexée

travailler avec les indices est une alternative qui est rapide et économe en mémoire et peut gérer n'importe quel nombre d'ensembles. La mise en œuvre itérable permet une utilisation facile dans une boucle pour chaque boucle. Voir le #méthode principale pour un exemple d'utilisation.

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

voici un itérable, qui vous permet d'utiliser une boucle simplifiée:

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

Comment est-ce fait? Nous avons besoin d'un itérable, pour utiliser la boucle simplifiée, et un itérateur doit être retourné de L'itérable. Nous retournons une liste d'objets - cela pourrait être un ensemble au lieu de List, mais Set n'a pas d'accès indexé, donc ce serait un peu plus compliqué, de l'implémenter avec Set au lieu de List. Au lieu d'une solution générique, l'Objet aurait été bien pour de nombreuses raisons, mais les génériques permettre plus de restrictions.

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

le travail mathématique se fait dans la méthode "get". Pensez à 2 ensembles de 10 éléments. Vous avez un total de 100 combinaisons, énumérées de 00, 01, 02, ... 10, ... à 99. Pour 5 X 10 éléments 50, pour 2 X 3 éléments 6 combinaisons. Le modulo de la taille de la sous-liste permet de choisir un élément pour chaque itération.

Itérable j'ai le moins de chose intéressante ici:

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

pour mettre en œuvre itérable, ce qui permet pour-chaque type de boucle, nous devons implémenter iterator (), et pour Iterator nous devons implémenter hasNext (), next () et remove ().

Résultat:

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

Oui, il y a Java Fonctionnel.

Pour une série (s):

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

l'empreinte mémoire (et traitement) nécessaire pour un produit cartésien peut devenir incontrôlable assez rapidement. L'implémentation naïve peut épuiser la mémoire et prendre beaucoup de temps. Il serait bon de connaître les opérations que vous prévoyez d'effectuer dans un tel ensemble, afin de proposer une stratégie de mise en œuvre.

dans tous les cas, faites quelque chose comme des décors.SetView sur google collections. C'est un jeu qui obtient adossés à d'autres séries comme ils ajouté. L'idée de leurs le problème est d'éviter l'appel addAll. L'idée de le problème est d'éviter de faire des additions NxMxK à un ensemble.

Google collections peuvent être trouvés ici et la catégorie est ici

Voici un Iterator qui donne le produit cartésien d'un tableau bidimensionnel, où les composants des tableaux représentent les ensembles de la question (on peut toujours convertir réel Sets pour les tableaux):

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'idée de base est de traiter count comme un nombre multi-radix (chiffre i a son propre rayon qui est égal à la longueur du i ' TH "set"). Chaque fois que nous avons à résoudre next (c'est-à-dire quand hasNext() est appelé et nextnull), nous décomposons le nombre dans ses chiffres dans ce multi-radix. Ces chiffres sont maintenant utilisés comme indices à partir desquels nous tirons des éléments des différents ensembles.

Exemple d'utilisation:

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

Sortie:

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

si on n'aime pas les tableaux, le code est trivialement convertible en utilisation de collections.

je suppose que c'est plus ou moins similaire à la réponse donnée par "utilisateur inconnu", seulement sans récursion et collections.