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
