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
