Java : Produit Cartésien d'une Liste de Listes

Essayer quelque chose comme cela:

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 permet d'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 sur la base (je crois) un de Knuth est TAOCP livres (dans les commentaires @chikitin a une référence plus précise: c'est dans PRÉ FASCICULE 2A de la section 7.2.1.1 de Générer Tous les n-tuple, de L'Art De la Programmation Informatique par Knuth, Addison Wesley).

Notez que j'ai nommé les tableaux set, mais ils n'ont pas besoin de détenir des éléments uniques, bien sûr. Le temps que je l'ai utilisé, ils contenaient des éléments uniques, d'où le nom.

MODIFIER

C'est à peu près d'un 1-sur-1 traduction:

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

Si vous exécutez la classe ci-dessus, le texte suivant est imprimé:

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

OriginalL'auteur Bart Kiers

Comment sur la génération de produit paresseusement, c'est à dire. seulement de créer le tuple lorsque vous avez accédé?

/**
* 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<T> with elements being treated as singletons
*
*/
abstract public class CartesianProductView<T> extends AbstractList<T> {
private final List<List<T>> 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<List<T>> factors) {
this.factors = new ArrayList<>(factors);
Collections.reverse(this.factors);
int acc = 1;
for (Iterator<List<T>> 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(String.format("index %d > size() %d", index, size()));
}
T acc = null;
for (Iterator<List<T>> iter = factors.iterator(); iter.hasNext();) {
List<T> 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 de l'utiliser comme ceci

final List<List<String>> l1 = new ArrayList<List<String>>() {{ add(singletonList("a")); add(singletonList("b")); add(singletonList("c")); }};
final List<List<String>> l2 = new ArrayList<List<String>>() {{ add(singletonList("X")); add(singletonList("Y")); }};
final List<List<String>> l3 = new ArrayList<List<String>>() {{ add(singletonList("1")); add(singletonList("2")); add(singletonList("3")); add(singletonList("4")); }};
List<List<List<String>>> in = new ArrayList<List<List<String>>>() {{ add(l1); add(l2); add(l3); }};
List<List<String>> a = new CartesianProductView<List<String>>(in) {
@Override
protected List<String> makeTuple(final List<String> left, final List<String> right) {
return new ArrayList<String>() {{ 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]]

Comme un bonus supplémentaire, vous pouvez l'utiliser à rejoindre les chaînes de tous avec tous:

final List<String> l1 = new ArrayList<String>() {{ add("a"); add("b"); add("c"); }};
final List<String> l2 = new ArrayList<String>() {{ add("X"); add("Y"); }};
final List<String> l3 = new ArrayList<String>() {{ add("1"); add("2"); add("3"); add("4"); }};
List<List<String>> in = new ArrayList<List<String>>() {{ add(l1); add(l2); add(l3); }};
List<String> a = new CartesianProductView<String>(in) {
@Override
protected String makeTuple(String left, String right) {
return String.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]

OriginalL'auteur Adrian Panasiuk

Vous pouvez également résoudre ce vraiment facilement avec Fonctionnel Java Liste monade:

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

OriginalL'auteur Shlomi

Ici est un lien, ses c#, mais je suis sûr que vous pourriez travailler avec!

OriginalL'auteur Shlomi

Je suis en retard à la fête, mais j'ai suivi Shiomi du lien et de traduire les fonctions en Java. Le résultat est un facile de suivre et de comprendre l'algorithme (j'ai peut-être un peu lent depuis que j'ai eu du mal à comprendre Bart Kiers solution).

Ici, c'est (la clé est un int, en remplacement de Chaîne doit être simple):

Utilisation

    public void testProduct(){
Map<Integer, List<String>> data =   new LinkedHashMap<Integer, List<String>>(){{                
put(0, new ArrayList<String>(){{
add("John"); add("Sarah");                      
}});                
put(1, new ArrayList<String>(){{
add("Red"); add("Green"); add("Blue"); add("Orange");
}});
put(2, new ArrayList<String>(){{
add("Apple"); add("Tomatoe"); add("Bananna");                   
}});
}};
List<String[]> product =  GetCrossProduct(data);
for(String[] o : product)
System.out.println(Arrays.toString(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]

Produit Cartésien Des Fonctions

    public static List<String[]> GetCrossProduct(Map<Integer, List<String>> lists)
{
List<String[]> results = new ArrayList<String[]>();
GetCrossProduct(results, lists, 0, new String[(lists.size())]);
return results;
}
private void GetCrossProduct(List<String[]> results, Map<Integer, List<String>> lists, int depth, String[] 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));                
}
}
}       

OriginalL'auteur Ulises