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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
