Anonymous user
Power set: Difference between revisions
→{{header|Java}}: Added iterative version of powerset for Java that perserves the input list.
m (→[[Power set#ALGOL 68]]: fix pre tag - segregate test) |
(→{{header|Java}}: Added iterative version of powerset for Java that perserves the input list.) |
||
Line 682:
return ans;
}</lang>
===Iterative===
The iterative implementation of the above idea. Each subset is in the order that the element appears in the input list. This implementation preserves the input.
<lang java5>
public static <T> List<List<T>> powerset(Collection<T> list) {
List<List<T>> ps = new ArrayList<List<T>>();
ps.add(new ArrayList<T>()); // add the empty set
// for every item in the original list
for (T item : list) {
List<List<T>> newPs = new ArrayList<List<T>>();
for (List<T> subset : ps) {
// copy all of the current powerset's subsets
newPs.add(subset);
// plus the subsets appended with the current item
List<T> newSubset = new ArrayList<T>(subset);
newSubset.add(item);
newPs.add(newSubset);
}
// powerset is now powerset of list.subList(0, list.indexOf(item)+1)
ps = newPs;
}
return ps;
}
</lang>
===Binary String===
This implementation works on idea that each element in the original set can either be in the power set or not in it. With <tt>n</tt> elements in the original set, each combination can be represented by a binary string of length <tt>n</tt>. To get all possible combinations, all you need is a counter from 0 to 2<sup>n</sup> - 1. If the k<sup>th</sup> bit in the binary string is 1, the k<sup>th</sup> element of the original set is in this combination.
| |||