Roger Hui wrote: > 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| > ++-+-+---+-+---+---+-----+-+---+---+-----+---+-----+-----+-------+ Thanks for this fine explanation!
Can't help it, but here's an illustration in speed difference between Haskell GHCi (interpreted) and J on this subject. ts 'it=:# ps2 i.20' 1.94006 1.53567e8 it 1048576 *Main> length . powerset $ [1..20] 1048576 (0.28 secs, 76022120 bytes) For those interested: powerset [] = [[]] powerset (x:xs) = p ++ map (x:) p where p = powerset xs Is it a challenge to speed up things in J? ;-) @@i ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
