Rosetta Code

Power set: Difference between revisions

Page Discussion

Power set (view source)

Revision as of 10:43, 18 July 2011

260 bytes removed ,  12 years ago
→‎Recursion
Line 889:
[[Category:Recursion]]
This implementation sorts each subset, but not the whole list of subsets (which would require a custom comparator). It also destroys the original set.
<lang java5>public static ArrayList<TString> extendsgetpowerset(int Comparable<?a[],int super T>> LinkedListn,ArrayList<LinkedList<T>String> powSet(ps)
{
LinkedList<T> A){
if(n<0)
LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>();
{
if(A.size() == 1){//if there's only one element, we know the answer
return null;
ans.add(new LinkedList<T>());//empty set
}
LinkedList<T> temp= new LinkedList<T>();
if(n==0)
temp.add(A.peekFirst());//and the only element in the original set
{
ans.add(temp);
if(ps==null)
}else{
ps=new ArrayList();
T first= A.removeFirst();//save the first element
ps.add(" ");
LinkedList<LinkedList<T>> partial= powSet(A);//recursion call
return ps;
for(LinkedList<T> subset: partial){//for each set in the partial set
}
ans.add(subset);//add it to the answer
ps=getpowerset(a, n-1, ps);
LinkedList<T> temp= new LinkedList<T>(subset);
ArrayList<String> tmp=new ArrayList<String>();
temp.add(first);//add the saved element to it
for(String s:ps)
Collections.sort(temp);//sort that set
{
ans.add(temp);//add the new set to the answer
if(s.equals(" "))
}
tmp.add(""+a[n-1]);
}
else
return ans;▼
tmp.add(s+a[n-1]);
}</lang>▼
}
ps.addAll(tmp);
▲ return ansps;
▲ }</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.
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/74257"