Java : Cartesian Product of a List of Lists

问题:

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. If this is an exact duplicate of a question however, please put a link in the response and I will close the question.

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.

回答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