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
