Is there a general pattern for solving a combination?
Suppose you have two sets, such as {a, b} xy {c, d, e}, return all combinations (axyc, axyd, axye, bxyc, bxyd, bxye). I know there is a similar one, but I am not satisfied with the answer Cartesian product of arbitrary sets in Java , my question is, if there is a general approach to solving it
+3
source to share
1 answer
Yes, there is an approach called "Backtracking", which is a common pattern for solving this problem. check here: http://en.wikipedia.org/wiki/Backtracking Below 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));
}
}
}
+2
source to share