Deepak
BAN USERThis is an iterative approach. We can similarly have a recursive approach by tweaking the code a little.
This is based on the definition of a power set (Wikipedia). A Power set is the union of all subsets of S containing a particular element as well as all subsets not containing that element. The code is based on the simple logic.
public class Test{
private List<List<String>> computePowerIterative(List<String> input){
List<List<String>> powerSet = new ArrayList<List<String>>();
powerSet.add(new ArrayList<String>());
for(int i=0;i<input.size();i++){
String item = input.get(i);
int numOfSetsWithoutItem = powerSet.size();
for(int j=0;j<numOfSetsWithoutItem;j++){
List<String>lst = powerSet.get(j);
List<String> lst1 = new ArrayList<String>();
lst1.addAll(lst);
lst1.add(item);
powerSet.add(lst1);
}
}
return powerSet;
}
private void printPowerSet(List<List<String>> powerSet){
for(List<String> lst : powerSet){
System.out.print("{");
for(String s : lst){
System.out.print(s);
}
System.out.print("}");
System.out.println();
}
}
public static void main(String[] args) {
List<String> input = new ArrayList<String>();
input.add("a");
input.add("b");
input.add("c");
input.add("d");
input.add("e");
Test test = new Test ();
List<List<String>> powerSet = test.computePowerIterative(input);
System.out.println("Size of power set " +powerSet.size());
test.printPowerSet(powerSet);
}
}
I believe the question was to generate a power set
- Deepak July 13, 2014