Is there a common pattern to solve combination?

Question

Suppose you have two sets, such as {a,b} xy {c,d,e}, return all the combinations (axyc, axyd, axye, bxyc, bxyd, bxye). I know there is a similar one, but I am not satisfied about answers Cartesian product of an arbitrary number of sets, my question is that if there is a common approach to solve it?

Answer 1

Yes, there is an approach called "Backtracking", it is a common pattern to solve this kind of problem. check it here: http://en.wikipedia.org/wiki/Backtracking

The following is the code:

public static void main(String[] args) {
    // TODO Auto-generated method stub
    List<List<Character>> lists = new ArrayList<List<Character>>();
    List<Character> l1 = new ArrayList<Character>();
    l1.add('a'); l1.add('b');; l1.add('c');
    List<Character> l2 = new ArrayList<Character>();
    l2.add('#');
    List<Character> l3 = new ArrayList<Character>();
    l3.add('1'); l3.add('2');
    lists.add(l1); lists.add(l2); lists.add(l3);

    List<String> result = new ArrayList<String>();
    GenerateCombinations(lists, result, 0, new StringBuilder());

    System.out.println(result);
}

public static void GenerateCombinations(List<List<Character>> Lists,
                                        List<String> result, int listIndex,
                                        StringBuilder combo) {
    if (listIndex == Lists.size()) {
        result.add(combo.toString());
    } else {
        for (int i = 0; i < Lists.get(listIndex).size(); ++i) {
            //add new value
            combo.append(Lists.get(listIndex).get(i));
            //get possible values in next list.
            GenerateCombinations(Lists, result, listIndex + 1, combo);
            //set back to old state.
            combo.deleteCharAt((combo.length() - 1));
        }
    }
}