Alternative formulations (but still exponential).
For the t here, the following are equivalent:
~. (~.i.])"1 t
t #~ ((i.x) -: ~.)"1 t
Thus:
ess1=: 4 : 0
t=. (y$x)#:i.x^y
t=. t #~ *./(y%x)=+/"1 (i.x)=/t
t #~ ((i.x) -: ~.)"1 t
)
Also, combining ess with ideas from Jordan Tirrell's original msg:
perm=: [EMAIL PROTECTED] A. i.
ess2=: 4 : 0
~. (~.i.])"1 (perm y){"_ 1 (y%x)#i.x
)
----- Original Message -----
From: Roger Hui <[EMAIL PROTECTED]>
Date: Wednesday, July 23, 2008 15:45
Subject: Re: RE: [Jprogramming] equal-size partitions
To: Programming forum <[email protected]>
> > To capture the required property that order within a
> > "partition" and the ordering of the "paritions" do not
> matter,
> > it's better to describe the problem as follows:
> > divide a set of n objects into k equal-sized subsets.
>
> There is a simple algorithm. It requires exponential
> time (and space) but is useful for checking the
> results of faster solutions.
>
> Generate the odometer t=. (n$k)#:i.k^n and select only
> those rows with exactly n%k occurrences of each integer.
> Apply ~. (~.i.])"1 t to remove duplicates. Thus:
>
> NB. equal sized subsets
> NB. all groupings of i. y into (y%x) size-x subsets
> ess=: 4 : 0
> t=. (y$x)#:i.x^y
> t=. t #~ *./(y%x)=+/"1 (i.x)=/t
> ~. (~.i.])"1 t
> )
>
> 2 ess 6
> 0 0 0 1 1 1
> 0 0 1 0 1 1
> 0 0 1 1 0 1
> 0 0 1 1 1 0
> 0 1 0 0 1 1
> 0 1 0 1 0 1
> 0 1 0 1 1 0
> 0 1 1 0 0 1
> 0 1 1 0 1 0
> 0 1 1 1 0 0
>
> 3 ess 6
> 0 0 1 1 2 2
> 0 0 1 2 1 2
> 0 0 1 2 2 1
> 0 1 0 1 2 2
> 0 1 0 2 1 2
> 0 1 0 2 2 1
> 0 1 1 0 2 2
> 0 1 1 2 0 2
> 0 1 1 2 2 0
> 0 1 2 0 1 2
> 0 1 2 0 2 1
> 0 1 2 1 0 2
> 0 1 2 1 2 0
> 0 1 2 2 0 1
> 0 1 2 2 1 0
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
