//Represents Set and its PowerSet as linked lists. //Elements in Set are linked via property down. //Subsets in PowerSet linked via property next. //Both Sets and PowerSets use the same class "Set". //Drawback is that link "next" is idle in Set objects. //Be aware: here, PowerSet of an empty set and empty set are //represented by the same node with down = next = null. //Algorithm is so simple that speaks for itself. //Copyright (c) 2010 Konstantin Kirillov. class Set{ Set down; //Links elements. Set next; //Links sets. Object element; //Top element of a set. public Set(){} //This creates an empty set. //Sugar constructor which converts array to our //representation of set: //Input: m is a position from wich to start // to add elements. // if m < 0, empty set is created. public Set( Object[] a, int m ){ if( m >=0 ){ Set s = new Set( a, m-1 ); element = a[m]; down = s; } } //Add element to this set and return new set: public Set append( Object element ){ Set s = new Set(); s.element = element; s.down = this; return s; } //======================================================================= // Core Algorithm //----------------------------------------------------------------------- public static Set createPowerSet(Set s){ if( s.down == null ) return new Set(); return createPowerSet(s.down).spawn(s.element); } //Spawns "this" PowerSet by adding single element to a all subsets //and returns new PowerSet: //Input: element - element to be added. public Set spawn( Object element ){ Set slider = this; Set first = this; while( slider != null ){ Set s = slider.append(element); s.next = first; first = s; slider = slider.next; } return first; } //----------------------------------------------------------------------- // Core Algorithm //======================================================================= //Displays ps. Traverses nodes "horizontally": public void displayAsFamily(){ Set slider=this; int count=0; while(slider != null ){ count++; pr("Subset "+ count + ". "); slider.displayAsSet(); slider=slider.next; } pr( " " ); } //Traverses nodes "vertically": public void displayAsSet(){ if( down == null ){ pr( " Empty" ); return; } Set slider=this; while(slider.down != null ){ slider.displayAsElement(); slider=slider.down; } pr(" "); } //Sugar: print element: public void displayAsElement(){ System.out.print( " "+element ); } //Auxiliary: public static void pr(Object ob){ System.out.println( ob ); } //=================================================================== //Test Case: //------------------------------------------------------------------- public static void main(String[] args){ int[] GivenSet = { 1, 2, 3, 4 }; Integer[] X=new Integer[GivenSet.length]; for(int i=0; i