Produit cartésien de l'arbitraire des jeux en Java

Edit: solutions Précédentes pour les deux ensembles supprimé. Voir l'historique des modifications pour plus de détails.

Ici est une façon de le faire de manière récursive pour un nombre arbitraire de jeux:

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

Noter qu'il est impossible de garder un type générique de l'information avec les ensembles renvoyés. Si vous saviez à l'avance le nombre de jeux que vous souhaitiez prendre le produit, vous pouvez définir un tuple générique de tenir que de nombreux éléments (par exemple Triple<A, B, C>), mais il n'existe aucun moyen d'avoir un nombre arbitraire de paramètres génériques en Java.

OriginalL'auteur Michael Myers

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

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

OriginalL'auteur Philipp Meister

Indice solution basée sur

De travail avec les indices sont une alternative rapide et efficace de la mémoire et peut gérer n'importe quel nombre de jeux. La mise en œuvre de Itératif permet de faciliter l'utilisation dans une boucle for-each. 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]]);
}
}
}

OriginalL'auteur Remko Popma

Voici un Iterator que donne le produit cartésien d'un tableau à deux dimensions, où les matrices de composants représentent les ensembles à partir de la question (on peut toujours convertir le 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 multi-radix nombre (chiffre i dispose de sa propre base, qui est égale à la longueur de la i'th "set"). Chaque fois que nous avons à résoudre next (qui est, quand hasNext() est appelé et next est null), on décompose le nombre en ses chiffres dans ce multi-radix. Ces chiffres sont maintenant utilisées comme des indices à partir de laquelle on tire des éléments de plusieurs 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));
}

De 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 convertibles en actions à l'aide de collections.

Je suppose que c'est plus ou moins similaire à la réponse donnée par "utilisateur inconnu", seul, sans récursivité et de collections.

OriginalL'auteur Halle Knast

La mémoire (et de traitement) de l'empreinte nécessaire pour un produit Cartésien peut sortir de la main assez rapidement. L'implémentation naïve peut d'échappement de la mémoire et de prendre beaucoup de temps. Il serait agréable de connaître les activités que vous envisagez de jouer dans un tel ensemble, afin de proposer une stratégie de mise en œuvre.

Dans tous les cas, faire quelque chose comme Jeux de.SetView sur google collections. C'est un jeu qui obtient adossés à d'autres séries comme ils ajouté. L'idée de leur problème, c'est pour éviter le addAll appel. L'idée de votre problème est d'éviter de faire NxMxK ajoute à un ensemble.

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

OriginalL'auteur H Marcelo Morales