To save space, it would also be posible to store the indices
and use #: to get the real thing, pretty much like A. for permutations,
when needed.
Oleg Kobchenko
On Aug 13, 2007, at 11:55 AM, Roger Hui <[EMAIL PROTECTED]> wrote:
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
____________________________________________________________________________________
Luggage? GPS? Comic books?
Check out fitting gifts for grads at Yahoo! Search
http://search.yahoo.com/search?fr=oni_on_mail&p=graduation+gifts&cs=bz
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
