If the subsets are differently grouped, more efficient solutions are possible:
(i. <@comb"0 ])5 ++-+---+-----+-------+ ||0|0 1|0 1 2|0 1 2 3| ||1|0 2|0 1 3|0 1 2 4| ||2|0 3|0 1 4|0 1 3 4| ||3|0 4|0 2 3|0 2 3 4| ||4|1 2|0 2 4|1 2 3 4| || |1 3|0 3 4| | || |1 4|1 2 3| | || |2 3|1 2 4| | || |2 4|1 3 4| | || |3 4|2 3 4| | ++-+---+-----+-------+ ts 'ps2 i.15' 0.051891392 4280704 ts'(i. <@comb"0 ])15' 0.0078416183 1611136 ts 'ps2 i.20' 2.238679 1.5356698e8 ts'(i. <@comb"0 ])20' 0.40906997 62709248 The author of comb definitely can improve this further. R.E. Boss > -----Oorspronkelijk bericht----- > Van: [EMAIL PROTECTED] [mailto:programming- > [EMAIL PROTECTED] Namens Roger Hui > Verzonden: maandag 13 augustus 2007 18:47 > Aan: Programming forum > Onderwerp: Re: [Jprogramming] Power sets > > ps2=: , @ ((] , ,&.>)/) @ (<@,:"_1 , a:"_) > > The initial ravel is necessary to make the powerset > a list for 0-item arguments. > > The steps of the algorithm: > > 3 (],,&.>) a: > ++-+ > ||3| > ++-+ > 2 (],,&.>) 3 (],,&.>) a: > ++-+-+---+ > ||3|2|2 3| > ++-+-+---+ > 1 (],,&.>) 2 (],,&.>) 3 (],,&.>) a: > ++-+-+---+-+---+---+-----+ > ||3|2|2 3|1|1 3|1 2|1 2 3| > ++-+-+---+-+---+---+-----+ > 0 (],,&.>) 1 (],,&.>) 2 (],,&.>) 3 (],,&.>) a: > ++-+-+---+-+---+---+-----+-+---+---+-----+---+-----+-----+-------+ > ||3|2|2 3|1|1 3|1 2|1 2 3|0|0 3|0 2|0 2 3|0 1|0 1 3|0 1 2|0 1 2 3| > ++-+-+---+-+---+---+-----+-+---+---+-----+---+-----+-----+-------+ > ps2 0 1 2 3 > ++-+-+---+-+---+---+-----+-+---+---+-----+---+-----+-----+-------+ > ||3|2|2 3|1|1 3|1 2|1 2 3|0|0 3|0 2|0 2 3|0 1|0 1 3|0 1 2|0 1 2 3| > ++-+-+---+-+---+---+-----+-+---+---+-----+---+-----+-----+-------+ > > > > ----- Original Message ----- > From: Roger Hui <[EMAIL PROTECTED]> > Date: Monday, August 13, 2007 8:55 > Subject: Re: [Jprogramming] Power sets > To: Programming forum <[email protected]> > > > Tacit version: > > > > ps1=: (,a:)"_ ` (<@((,0)&{) (] , ,&.>) $:@}.) @. (0<#) > > > > > > > > ----- Original Message ----- > > From: Roger Hui <[EMAIL PROTECTED]> > > Date: Monday, August 13, 2007 8:48 > > Subject: Re: [Jprogramming] Power sets > > To: Programming forum <[email protected]> > > > > > A recursive version: > > > > > > ps=: 3 : 'if. 0=#y do. ,a: else. (<(,0){y) (] , ,&.>) ps > > }.y end.' > > > > > > ps i.3 > > > ++-+-+---+-+---+---+-----+ > > > ||2|1|1 2|0|0 2|0 1|0 1 2| > > > ++-+-+---+-+---+---+-----+ > > > ps >;:'zero one two' > > > ++----+----+----+----+----+----+----+ > > > ||two |one |one |zero|zero|zero|zero| > > > || | |two > > > | |two |one |one | > > > || | | > > > | | | > > |two | > > > || | | > > > | | | > > > | | > > > ++----+----+----+----+----+----+----+ > > > > > > (ps -: powerset) i.16 > > > 1 > > > ts 't=: ps i.16' > > > 0.236343 8.8887e6 > > > ts 't=: powerset i.16' > > > 0.234749 1.55797e7 > > > 7!:5 <'t' > > > 7959744 > > > > > > The last sentence indicates that ps does not use > > > much space in excess of that needed for the result. > > > However, it is in the nature of powersets that the > > > space (and time) grows exponentially as #y . > > > > > > > > > > > > ----- Original Message ----- > > > From: Arie Groeneveld <[EMAIL PROTECTED]> > > > Date: Monday, August 13, 2007 4:56 > > > Subject: [Jprogramming] Power sets > > > To: Programming forum <[email protected]> > > > > > > > Hi, > > > > > > > > > > > > To generate all subsets of set s: > > > > this is what I can come up with: > > > > > > > > powerset=: 13 : '(#: i.2^#y)<@:#"1 y' > > > > > > > > a =: 1 2 3 4 > > > > > > > > powerset a > > > > ++-+-+---+-+---+---+-----+-+---+---+-----+---+-----+-----+--- > > -- > > > --+ > > > > ||4|3|3 4|2|2 4|2 3|2 3 4|1|1 4|1 3|1 3 4|1 2|1 2 4|1 2 3|1 > > 2 > > > 3 4| > > > > ++-+-+---+-+---+---+-----+-+---+---+-----+---+-----+-----+--- > > -- > > > --+ > > > > > > > > ... and: > > > > > > > > ts 'it=:powerset 1+ i.20' > > > > 2.73689 2.60676e8 > > > > #it > > > > 1048576 > > > > > > > > Can someone produce another verb 'powerset' because > > > > it looks to me that I use to much resources. > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
