Power set: Difference between revisions

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 <T ~~extends~~ ~~Comparable<?~~ ~~super T>> LinkedList~~<~~LinkedList<T>~~> ~~powSet(~~

<lang java5>public static ArrayList<String> getpowerset(int a[],int n,ArrayList<String> 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 ps;

⚫

}</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.