Given a set of unique characters, generate its superset. example: a, b, c, its superset are:
[[], [c], [b], [c, b], [a], [c, a], [b, a], [c, b, a]]
There are two ways to solve this problem,
one is by recursion, basically we generate a set for a, then append b to each element, which itself is a set too, in the set, adding back to the set; then append c to each element in the new set and adding back to the set.
{}
{}, {a}
{b}, {a,b}, {}, {a}
{b,c{,{a,b,c},{c},{a,c},{b},{a,b},{},{a}
private static List<List<Character>> getSuperSetRec(char[] chars, int index){
if(index == chars.length){
List<List<Character>> list = new ArrayList<List<Character>>();
List<Character> l = Collections.emptyList();
list.add(l);
return list;
}
else{
List<List<Character>> list = getSuperSetRec(chars, index+1);
List<List<Character>> res = new ArrayList<List<Character>>(list);
for(List<Character> l : list){
List<Character> temp = new ArrayList<Character>(l);
temp.add(chars[index]);
res.add(temp);
}
return res;
}
}
the second approach is very interesting. We use binary number to present each subset, 1 at any position of the binary number means the character at that position exists in the subset, e.g. 1 1 1 corresponding to {a,b,c}, 1 0 0 corresponding to {a}, so we can use 2^3 numbers to represent each subset, the problem becomes to find on every position of the binary number if it is 1 or 0.
public static void printSuperSetIteratively(char[] chars){
int size = chars.length;
int superSetSize = (int)Math.pow(2, size);
List<List<Character>> list2 = new ArrayList<List<Character>>();
for(int i=0; i<superSetSize; i++){
List<Character> list = new ArrayList<Character>();
for(int j=0; j<size; j++){
if((i&1<<j)>0){
list.add(chars[j]);
}
}
list2.add(list);
}
System.out.println(list2);
}
No comments:
Post a Comment