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
