This will be my last post on this discussion. You are barking up the wrong tree. Of course I agree that different representations cause different, often incomparable performances. But our common choice was to represent the subsets by its members, in increasing order. You boxed each subset, I boxed them according to their size, as I showed before. IMO you unjustifiable exaggerate that difference in boxing, if you compare it with representations like i.@(2&^) or #:@i.@(2&^)
What's more, if the output of ps4 is adapted to your "representation" of ps2, its still a lot faster and slightly uses more space: ts'ps2 i.20' 2.070133 1.5356698e8 ts';<"1&.>ps4 20' 0.83120811 2.027927e8 (ps2 i.20) -:&(/:~) ;<"1&.>ps4 20 1 ts'ps4 20' NB. for reference 0.20777946 63326336 Or do you still insist the representations to be incomparable because they are sorted differently? This discussion I will not continue since all my arguments should be known by now. Let the readers judge for themselves. Apart from that, it costs me a lot of effort to have a discussion in a foreign language in which I cannot express myself as eloquently as in my own. That said (as Miller would say), it's much more fun to build original, elegant and fast algorithms in J, especially if they perform better than known ones. R.E. Boss > -----Oorspronkelijk bericht----- > Van: [EMAIL PROTECTED] [mailto:programming- > [EMAIL PROTECTED] Namens Roger Hui > Verzonden: woensdag 15 augustus 2007 19:41 > Aan: Programming forum > Onderwerp: Re: RE: [Jprogramming] Power sets > > > Further > > > > ts 'ps2 i.20' > > 2.0541071 1.5356698e8 > > ts 'ps4 20' > > 0.21588886 63326336 > > > > ([EMAIL PROTECTED]:&(\:~)[:;[:<"1&.>ps4) 20 > > 1 > > Using the same rules as you are employing: > > ps5=: ] > (ps4 -: [: (i.@>: comb&.> ]) ps5) 20 > 1 > > ts 'ps4 20' > 0.54264 6.33263e7 > ts 'ps5 20' > 7.82222e_6 832 > > You don't like that? How about: > > ps6=: i.@(2&^) > ps7=: #:@i.@(2&^) > > ts 'ps6 20' > 0.0105044 8.38957e6 > ts 'ps7 20' > 0.0712065 4.1944e7 > > The representations in ps6 and ps7 (and ps5, for that > matter) fully represent the power set of i.20: > In i.2^20 the integers have the bit patterns that > full specify the power set of i.20. Likewise in > the rows in #:i.2^20. > > > > ----- Original Message ----- > From: "R.E. Boss" <[EMAIL PROTECTED]> > Date: Wednesday, August 15, 2007 6:52 > Subject: RE: [Jprogramming] Power sets > To: 'Programming forum' <[email protected]> > > > I am not. > > > > Its the same kind of fruit, only stored differently, as the > > following shows. > > > > ps2 > > i.4 NB. your solution > > ++-+-+---+-+---+---+-----+-+---+---+-----+---+-----+-----+-------+ > > ||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| > > ++-+-+---+-+---+---+-----+-+---+---+-----+---+-----+-----+-------+ > > ps4 > > 4 NB. my solution > > ++-+---+-----+-------+ > > ||0|0 1|0 1 2|0 1 2 3| > > ||1|0 2|0 1 3| | > > ||2|0 3|0 2 3| | > > ||3|1 2|1 2 3| | > > || |1 3| > > | | > > || |2 3| > > | | > > ++-+---+-----+-------+ > > > > So, contrary to what you write, its both "interesting" and > > "informative to > > compare the time/space needed to compute them". > > > > > > R.E. Boss > > > > > > > > > -----Oorspronkelijk bericht----- > > > Van: [EMAIL PROTECTED] [mailto:programming- > > > [EMAIL PROTECTED] Namens Roger Hui > > > Verzonden: dinsdag 14 augustus 2007 23:11 > > > Aan: Programming forum > > > Onderwerp: Re: [Jprogramming] Power sets > > > > > > 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&.> #) {&.> <@] > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
