java - Cartesian Product of a List of Lists

Question

I have a problem that is really kind of a general programming question, but my implementation is in Java, so I will provide my examples that way

I have a class like this:

public class Foo {
    LinkedHashMap<String, Vector<String>> dataStructure;

    public Foo(LinkedHashMap<String, Vector<String>> dataStructure) {
        this.dataStructure = dataStructure;
    }

    public String[][] allUniqueCombinations() {
        //this is what I need to do
    }
}

I need to generate a nested array from my LinkedHashMap that represents every unique combination of all values in the LHM. for example, if my LHM looks like this (pseudocode, but I think you can get the idea..):

{"foo" => ["1","2","3"], "bar" => ["3","2"], "baz" => ["5","6","7"]};

then my String[][] should look like this:

{
   {"foo","bar","baz"},
   {"1","3","5"},
   {"1","2","5"},
   {"1","3","6"},
   {"1","2","6"},
   {"1","3","7"},
   {"1","2","7"},
   {"2","3","5"},
   {"2","2","5"},
   {"2","3","6"},
   {"2","2","6"},
   {"2","3","7"},
   {"2","2","7"},
   {"3","3","5"},
   {"3","2","5"},
   {"3","3","6"},
   {"3","2","6"},
   {"3","3","7"},
   {"3","2","7"},
}

I think that's all of them, I made that manually (obviously) so I might have missed a set, but I think this illustrates what I'm trying to do. It doesn't matter what order each set comes in, so long as all unique combinations are present. Also to be clear, you don't know how many elements are in the LHM, nor how many elements are in each subsequent Vector. I have found answers that match the case where you want every unique combination of all elements in a single array, but nothing that fits this exactly.

Update: I changed my types to strings because my real world example is actually strings. I was trying to use integers to make the example more readable, but the answers I've gotten so far do not translate well to strings. So, yes they are numbers, but in my actual case, they will be strings that wouldn't make much sense to anyone but people who use this particular application. so, this is just an abstraction of it.

Answer 1

Try something like this:

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

which will print:

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

I've implemented the algorithm above based on (I believe) one of Knuth's TAOCP books (in the comments @chikitin has a more specific reference: it is in?????? ????PRE FASCICLE 2A section 7.2.1.1 Generating All n-tuple, of The Art Of Computer Programming by Knuth, Addison Wesley).

Note that I've named the arrays set, but they needn't hold unique elements, of course. The time I used it, they did contain unique elements, hence the name.

EDIT

It's pretty much a 1-on-1 translation:

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

If you run the class above, the following is printed:

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