You are comparing apples to oranges.
----- Original Message ----- From: "R.E. Boss" <[EMAIL PROTECTED]> Date: Tuesday, August 14, 2007 13:37 Subject: RE: RE: [Jprogramming] Power sets To: 'Programming forum' <[email protected]> > Since I was not talking about representations, but (different) > groupings (of > subsets) your first remark is highly irrelevant. > > Your second remark is answered by the solution you gave. > ps3 is still a lot more efficient than ps2: > ts'ps2 ''abcdefghijklmnopqrst''' > 1.3516162 90327552 > ts'ps3 ''abcdefghijklmnopqrst''' > 0.57262191 1.2099904e8 > > But improvement is still possible. > Using the idea of comb I constructed > ps4=: 3 : '(}:,;&.>@{:) (}:, > [:({.,<@([EMAIL PROTECTED],.&.>])@}.)[:,&.>/\.>@{:)^:y(y$<i.0 > 0)<@,<i.1 0' NB. line wrap! > and > ps4a=: ([:ps4 #) {&.> <@] NB. for nouns which are not an > integer atom > > ts'ps4a ''abcdefghijklmnopqrst''' > 0.37404972 1.2099936e8 > > (ps2-:&(\:~)[:;[:<"1&.>ps4a) 'abcdefghijklmnopqrst' > 1 > > Further > > ts 'ps2 i.20' > 2.0541071 1.5356698e8 > ts 'ps4 20' > 0.21588886 63326336 > > ([EMAIL PROTECTED]:&(\:~)[:;[:<"1&.>ps4) 20 > 1 > > ps4 seems faster than the Haskell solution, which was about 7 > times as fast. > > R.E. Boss > > > > > -----Oorspronkelijk bericht----- > > Van: [EMAIL PROTECTED] [mailto:programming- > > [EMAIL PROTECTED] Namens Roger Hui > > Verzonden: dinsdag 14 augustus 2007 18:50 > > Aan: Programming forum > > Onderwerp: Re: RE: [Jprogramming] Power sets > > > > It is interesting to compare different representations > > of the power set but not overly informative to compare > > the time/space needed to compute them. Moreover, > > it can be argued that #:i.2^n or even i.2^n represent > > the power set pretty well, and: > > > > ts '(i.@>: <@comb"0 ]) 15' > > 0.0135685 1.61126e6 > > ts 'i.2^15' > > 3.43619e_5 262912 > > > > At the very least, to make ps2 and the comb > > approach comparable, you have to make the > > latter work on arbitrary sets, such as 'abcd' or > > i.3 2 2. For example, > > > > ps3=: (i.@>:@# comb&.> #) {&.> <@] > > > > > > > > ----- Original Message ----- > > From: "R.E. Boss" <[EMAIL PROTECTED]> > > Date: Tuesday, August 14, 2007 3:09 > > Subject: RE: [Jprogramming] Power sets > > To: 'Programming forum' <[email protected]> > > > > > 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
