Java: produit cartésien d’une liste de listes

Essayez quelque chose comme ça:

 public static void generate(int[][] sets) { int solutions = 1; for(int i = 0; i < sets.length; solutions *= sets[i].length, i++); for(int i = 0; i < solutions; i++) { int j = 1; for(int[] set : sets) { System.out.print(set[(i/j)%set.length] + " "); j *= set.length; } System.out.println(); } } public static void main(String[] args) { generate(new int[][]{{1,2,3}, {3,2}, {5,6,7}}); } 

qui va imprimer:

 1 3 5 2 3 5 3 3 5 1 2 5 2 2 5 3 2 5 1 3 6 2 3 6 3 3 6 1 2 6 2 2 6 3 2 6 1 3 7 2 3 7 3 3 7 1 2 7 2 2 7 3 2 7 

J'ai implémenté l'algorithme ci-dessus basé sur (je crois) l'un des livres TAOCP de Knuth (dans les commentaires, @chikitin a une référence plus spécifique: il s'agit de la section 􏰓􏰔PRE FASCICLE 2A section 7.2.1.1 Générer tout n-tuple , de l’art de la programmation informatique de Knuth, Addison Wesley).

Notez que j'ai nommé l' set tableaux, mais ils n'ont pas besoin de contenir des éléments uniques, bien sûr. À l'époque où je l'ai utilisé, ils contenaient des éléments uniques, d'où son nom.

MODIFIER

C'est à peu près une traduction individuelle:

 import java.util.Arrays; import java.util.LinkedHashMap; import java.util.Vector; public class Foo { private LinkedHashMap> dataStructure; public Foo(LinkedHashMap> dataStructure){ this.dataStructure = dataStructure; } public Ssortingng[][] allUniqueCombinations(){ int n = dataStructure.keySet().size(); int solutions = 1; for(Vector vector : dataStructure.values()) { solutions *= vector.size(); } Ssortingng[][] allCombinations = new Ssortingng[solutions + 1][]; allCombinations[0] = dataStructure.keySet().toArray(new Ssortingng[n]); for(int i = 0; i < solutions; i++) { Vector combination = new Vector(n); int j = 1; for(Vector vec : dataStructure.values()) { combination.add(vec.get((i/j)%vec.size())); j *= vec.size(); } allCombinations[i + 1] = combination.toArray(new Ssortingng[n]); } return allCombinations; } public static void main(Ssortingng[] args) { LinkedHashMap> data = new LinkedHashMap>(); data.put("foo", new Vector(Arrays.asList("1", "2", "3"))); data.put("bar", new Vector(Arrays.asList("3", "2"))); data.put("baz", new Vector(Arrays.asList("5", "6", "7"))); Foo foo = new Foo(data); for(Ssortingng[] combination : foo.allUniqueCombinations()) { System.out.println(Arrays.toSsortingng(combination)); } } } 

Si vous exécutez la classe ci-dessus, les éléments suivants sont imprimés:

 [foo, bar, baz] [1, 3, 5] [2, 3, 5] [3, 3, 5] [1, 2, 5] [2, 2, 5] [3, 2, 5] [1, 3, 6] [2, 3, 6] [3, 3, 6] [1, 2, 6] [2, 2, 6] [3, 2, 6] [1, 3, 7] [2, 3, 7] [3, 3, 7] [1, 2, 7] [2, 2, 7] [3, 2, 7] 

Je sais que cela fait longtemps que vous avez besoin de la réponse, mais je ne peux toutefois pas m’empêcher de remarquer qu’on pourrait passer à Groovy, du moins pour une partie d’une application Java, et écrire une classe wrapper correspondant à l’interface souhaitée. Le code Groovy pour ces permutations est

 myListOfLists.combinations() 

Depuis que j’ai commencé à utiliser Groovy dans mes applications Java, il est beaucoup plus rapide de les écrire et beaucoup plus intéressant de les déboguer / les profiler (ehem …)

Que diriez-vous de générer le produit paresseusement, à savoir. créer le tuple uniquement lorsque vous y accédez?

 /** * A random access view of tuples of a cartesian product of ArrayLists * * Orders tuples in the natural order of the cartesian product * * @param T the type for both the values and the stored tuples, ie. values of the cartesian factors are singletons * While the type of input sets is List with elements being treated as singletons * */ abstract public class CartesianProductView extends AbstractList { private final List> factors; private final int size; /** * @param factors the length of the factors (ie. the elements of the factors argument) should not change, * otherwise get may not return all tuples, or throw exceptions when trying to access the factors outside of range */ public CartesianProductView(List> factors) { this.factors = new ArrayList<>(factors); Collections.reverse(this.factors); int acc = 1; for (Iterator> iter = this.factors.iterator(); iter.hasNext(); ) { acc *= iter.next().size(); } this.size = acc; } @Override public T get(int index) { if (index < 0 || index >= size()) { throw new IndexOutOfBoundsException(Ssortingng.format("index %d > size() %d", index, size())); } T acc = null; for (Iterator> iter = factors.iterator(); iter.hasNext();) { List set = iter.next(); acc = makeTupleOrSingleton(set.get(index % set.size()), acc); index /= set.size(); } return acc; } @Override public int size() { return size; } private T makeTupleOrSingleton(T left, T right) { if (right == null) { return left; } return makeTuple(left, right); } /** * * @param left a singleton of a value * @param right a tuple of values taken from the cartesian product factors, with null representing the empty set * @return the sum of left and right, with the value of left being put in front */ abstract protected T makeTuple(T left, T right); } 

et l’utiliser comme ça

 final List> l1 = new ArrayList>() {{ add(singletonList("a")); add(singletonList("b")); add(singletonList("c")); }}; final List> l2 = new ArrayList>() {{ add(singletonList("X")); add(singletonList("Y")); }}; final List> l3 = new ArrayList>() {{ add(singletonList("1")); add(singletonList("2")); add(singletonList("3")); add(singletonList("4")); }}; List>> in = new ArrayList>>() {{ add(l1); add(l2); add(l3); }}; List> a = new CartesianProductView>(in) { @Override protected List makeTuple(final List left, final List right) { return new ArrayList() {{ add(left.get(0)); addAll(right); }}; } }; System.out.println(a); 

Le résultat:

 [[a, X, 1], [a, X, 2], [a, X, 3], [a, X, 4], [a, Y, 1], [a, Y, 2], [a, Y, 3], [a, Y, 4], [b, X, 1], [b, X, 2], [b, X, 3], [b, X, 4], [b, Y, 1], [b, Y, 2], [b, Y, 3], [b, Y, 4], [c, X, 1], [c, X, 2], [c, X, 3], [c, X, 4], [c, Y, 1], [c, Y, 2], [c, Y, 3], [c, Y, 4]] 

En prime, vous pouvez l’utiliser pour joindre toutes les chaînes:

 final List l1 = new ArrayList() {{ add("a"); add("b"); add("c"); }}; final List l2 = new ArrayList() {{ add("X"); add("Y"); }}; final List l3 = new ArrayList() {{ add("1"); add("2"); add("3"); add("4"); }}; List> in = new ArrayList>() {{ add(l1); add(l2); add(l3); }}; List a = new CartesianProductView(in) { @Override protected Ssortingng makeTuple(Ssortingng left, Ssortingng right) { return Ssortingng.format("%s%s", left, right); } }; System.out.println(a); 

Le résultat:

 [aX1, aX2, aX3, aX4, aY1, aY2, aY3, aY4, bX1, bX2, bX3, bX4, bY1, bY2, bY3, bY4, cX1, cX2, cX3, cX4, cY1, cY2, cY3, cY4] 

Jetez un oeil aux deux méthodes suivantes, elles font exactement ce que vous avez demandé. Je leur ai écrit pour être générique, peu importe combien de temps vos listes sont ou combien de clés existent dans la carte, les combinaisons générées sont correctes.

Le code ci-dessous est itératif , basé sur l’algorithme de la fonction itertools.product() de Python pour calculer le produit cartésien d’une liste de listes.

 public Ssortingng[][] allUniqueCombinations() { List labels = new ArrayList(); List> lists = new ArrayList>(); for (Map.Entry> entry : dataStructure.entrySet()) { labels.add(entry.getKey()); lists.add(entry.getValue()); } List> combinations = product(lists); int m = combinations.size() + 1; int n = labels.size(); Ssortingng[][] answer = new Ssortingng[m][n]; for (int i = 0; i < n; i++) answer[0][i] = labels.get(i); for (int i = 1; i < m; i++) for (int j = 0; j < n; j++) answer[i][j] = combinations.get(i-1).get(j); return answer; } private List> product(List> lists) { List> result = new ArrayList>(); result.add(new ArrayList()); for (List e : lists) { List> tmp1 = new ArrayList>(); for (List x : result) { for (Ssortingng y : e) { List tmp2 = new ArrayList(x); tmp2.add(y); tmp1.add(tmp2); } } result = tmp1; } return result; } 

Je les ai testés avec l’exemple de la question:

 LinkedHashMap> sample = new LinkedHashMap>(); Vector v1 = new Vector(); v1.add("1"); v1.add("2"); v1.add("3"); Vector v2 = new Vector(); v2.add("3"); v2.add("2"); Vector v3 = new Vector(); v3.add("5"); v3.add("6"); v3.add("7"); sample.put("foo", v1); sample.put("bar", v2); sample.put("baz", v3); Foo foo = new Foo(sample); Ssortingng[][] ans = foo.allUniqueCombinations(); for (Ssortingng[] row : ans) System.out.println(Arrays.toSsortingng(row)); 

La réponse imprimée est celle attendue (bien que les combinaisons apparaissent dans un ordre différent):

 [foo, bar, baz] [1, 3, 5] [1, 3, 6] [1, 3, 7] [1, 2, 5] [1, 2, 6] [1, 2, 7] [2, 3, 5] [2, 3, 6] [2, 3, 7] [2, 2, 5] [2, 2, 6] [2, 2, 7] [3, 3, 5] [3, 3, 6] [3, 3, 7] [3, 2, 5] [3, 2, 6] [3, 2, 7] 

Vous pouvez également résoudre ce problème très facilement avec la monade List de Java fonctionnel :

 import fj.data.List; public class cartesian { public static void main(Ssortingng[] args) { List foo = List.list("a", "b"); List bar = List.list(1,2,3); List baz = List.list(0.2f,0.4f,0.3f); List> // the Cartesian product is assembled into a list of P3's result = foo.bind(bar, baz, P.p3()); Ssortingng out = Show.listShow(Show.p3Show(Show.ssortingngShow, Show.intShow, Show.floatShow)) .showS(result); System.out.println(out); } } 

Guava a une méthode utilitaire qui renvoie un produit cartésien de la liste d’ensembles donnée : Sets.cartesianProduct .

Voici un lien , son c #, mais je suis sûr que vous pourriez travailler avec ça!

Un LinkedHashMap de vecteurs de chaînes est … – gênant. Je devais passer beaucoup de temps à convertir une solution pour l’utiliser, mais au final, je ne produisais pas un ArrayOfArrays, mais une liste de liste et gardais la dernière étape pour le lecteur.

 import java.util.*; /** CartesianProductLHM */ public class CartesianProductLHM { LinkedHashMap > dataStructure; public CartesianProductLHM (final Ssortingng[] data) { dataStructure = new LinkedHashMap > (); for (Ssortingng str : data) { Ssortingng [] kv = str.split (":"); Ssortingng [] values = kv[1].split (","); Vector  v = new Vector  (); for (Ssortingng s: values) { v.add (s); // System.out.print (s); } // System.out.println ("\n---"); dataStructure.put (kv[0], v); } // System.out.println (" --- --- ---"); } List  getCombiFor (final int i, final List > livs) { List  ls = new ArrayList  (); if (! livs.isEmpty ()) { List  vs = livs.remove (0); int idx = i % vs.size (); Ssortingng elem = vs.get (idx); ls.add (elem); ls.addAll (getCombiFor (i / vs.size (), livs)); } return ls; } List  getOuterCombiFor (int i, List > coll) { List  ls = new ArrayList  (); if (! coll.isEmpty ()) { List > livs = new ArrayList > (); for (List li : coll) { livs.add (li); } ls.addAll (getCombiFor (i, livs)); } return ls; } public List > allUniqueCombinations () { Collection > li = dataStructure.values (); List > lls = new ArrayList > (); for (Vector  vs : li) { List  l = new ArrayList  (); for (Ssortingng s : vs) { l.add (s); } lls.add (l); } int count = 1; for (Vector  vec: li) { count *= vec.size (); } List > result = new ArrayList > (); for (int i = 0; i < count; ++i) { List  l = getOuterCombiFor (i, lls); result.add (l); } return result; } public static void main (Ssortingng args[]) { Ssortingng[] arr = {"foo:1,2,3", "bar:a,b", "baz:5,6,7"}; CartesianProductLHM cp = new CartesianProductLHM (arr); List > lls = cp.allUniqueCombinations (); for (List  ls : lls) { for (Ssortingng s : ls) System.out.print (s + "\t"); System.out.println (); } } } 

Eh bien – oui, et j’parsing des données de test.

L’idée principale est que vous avez des listes (abc, 12, defg, …) et que vous avez 3 possibilités au pos 0, 2 au pos 1, 4 au pos 3 et ainsi de suite, donc 3 * 2 * 4 combinaisons jusque là.

Parmi les nombres de 0 à 23, vous pouvez choisir dans chaque sous-liste avec modulo et remettre le rest du nombre divisé par la taille de la liste précédente et les listes restantes de manière récursive à la procédure, jusqu’à ce qu’il ne rest plus de liste.

Je suis en retard à la soirée mais j’ai suivi le lien de Shiomi et traduit les fonctions en Java. Le résultat est un algorithme facile à suivre et à comprendre (je peux être un peu lent car j’ai eu du mal à comprendre la solution de Bart Kiers).

La voici (la clé est un int, remplacer par Ssortingng devrait être simple):

Usage

  public void testProduct(){ Map> data = new LinkedHashMap>(){{ put(0, new ArrayList(){{ add("John"); add("Sarah"); }}); put(1, new ArrayList(){{ add("Red"); add("Green"); add("Blue"); add("Orange"); }}); put(2, new ArrayList(){{ add("Apple"); add("Tomatoe"); add("Bananna"); }}); }}; List product = GetCrossProduct(data); for(Ssortingng[] o : product) System.out.println(Arrays.toSsortingng(o)); } 

Résultat

 [John, Red, Apple] [John, Red, Tomatoe] [John, Red, Bananna] [John, Green, Apple] [John, Green, Tomatoe] [John, Green, Bananna] [John, Blue, Apple] [John, Blue, Tomatoe] [John, Blue, Bananna] [John, Orange, Apple] [John, Orange, Tomatoe] [John, Orange, Bananna] [Sarah, Red, Apple] [Sarah, Red, Tomatoe] [Sarah, Red, Bananna] [Sarah, Green, Apple] [Sarah, Green, Tomatoe] [Sarah, Green, Bananna] [Sarah, Blue, Apple] [Sarah, Blue, Tomatoe] [Sarah, Blue, Bananna] [Sarah, Orange, Apple] [Sarah, Orange, Tomatoe] [Sarah, Orange, Bananna] 

Fonctions de produit cartésiennes

  public static List GetCrossProduct(Map> lists) { List results = new ArrayList(); GetCrossProduct(results, lists, 0, new Ssortingng[(lists.size())]); return results; } private void GetCrossProduct(List results, Map> lists, int depth, Ssortingng[] current) { for (int i = 0; i < lists.get(depth).size(); i++) { current[depth] = lists.get(depth).get(i); if (depth < lists.keySet().size() - 1) GetCrossProduct(results, lists, depth + 1, current); else{ results.add(Arrays.copyOf(current,current.length)); } } } 

Vous pouvez générer les combinaisons de manière récursive.

 public class Main { public static void main(Ssortingng[] args) { int[][] arr = new int[][] { { 1, 2, 3 }, { 3, 2 }, { 5, 6, 7 } }; cartesianProduct(arr, 0, new int[arr.length]); } private static void cartesianProduct(int[][] arr, int level, int[] cp) { if (level == arr.length) { for (int x : cp) System.out.print(x + " "); System.out.println(); return; } for (int i = 0; i < arr[level].length; i++) { cp[level] = arr[level][i]; cartesianProduct(arr, level + 1, cp); } } } 

Sortie:

 1 3 5 1 3 6 1 3 7 1 2 5 1 2 6 1 2 7 2 3 5 2 3 6 2 3 7 2 2 5 2 2 6 2 2 7 3 3 5 3 3 6 3 3 7 3 2 5 3 2 6 3 2 7