[R] Finding all possible partitions of N units into k classe

Tuszynski, Jaroslaw W. JAROSLAW.W.TUSZYNSKI at saic.com
Thu Dec 8 20:20:17 CET 2005

```See Also
http://finzi.psych.upenn.edu/R/library/caTools/html/combs.html

Jarek Tuszynski

-----Original Message-----
From: r-help-bounces at stat.math.ethz.ch
[mailto:r-help-bounces at stat.math.ethz.ch]
Sent: Thursday, December 08, 2005 11:19 AM
To: Ales Ziberna
Cc: R-help
Subject: Re: [R] Finding all possible partitions of N units into k classe

On 08-Dec-05 Ales Ziberna wrote:
> Dear useRs!
>
> I would like to generate a list of all possible (unique)
> partitions of N units into k classes. For example, all possible
> partitions of 4 units into 2 classes are (I hope I have not
> missed anyone):
>
> 1,1,1,2 (this can be read as {1,2,3},{4})
> 1,1,2,1
> 1,2,1,1
> 2,1,1,1
> 1,1,2,2
> 1,2,1,2
> 1,2,2,1
>
> The partitions 1,1,2,2 and 2,2,1,1 are the same and are
> therefore not two unique partitions.

... which seems to imply that 2,1,1,1 and 1,2,2,2 are the same,
so I would write your list above as

> 1,1,1,2 (this can be read as {1,2,3},{4})
> 1,1,2,1
> 1,2,1,1
> 1,2,2,2
> 1,1,2,2
> 1,2,1,2
> 1,2,2,1

which should be a clue!

Fix the class to which unit "1" belongs as Class 1. This
leaves the partitioning of units 2:N, of which there are
2^(N-1) except that you want to exclude the case where they
all go into Class 1. So 2^(N-1) -1.

So let K = 1:(2^(N-1)-1), and for each k in K make the binary
representation of k. Say this gives N-1 binary digits

i1 i2 ... i[N-1]

(note that none of these will have all binary digits = 0).

Then assign unit "j+1" to Class 1 if ij = 0, otherwise to
Class 2.

However, that is if you want to do it with your bare hands!
The package combinat contains also the function 'hcube' which
generates all the 2^N combinations of the above).

library(combinat)
?hcube

x<-rep(2,4) # for partitions of 4 units into classes {1,2}

hcube(x,scale=1,transl=0)
#       [,1] [,2] [,3] [,4]
#  [1,]    1    1    1    1
#  [2,]    2    1    1    1
#  [3,]    1    2    1    1
#  [4,]    2    2    1    1
#  [5,]    1    1    2    1
#  [6,]    2    1    2    1
#  [7,]    1    2    2    1
#  [8,]    2    2    2    1
#  [9,]    1    1    1    2
# [10,]    2    1    1    2
# [11,]    1    2    1    2
# [12,]    2    2    1    2
# [13,]    1    1    2    2
# [14,]    2    1    2    2
# [15,]    1    2    2    2
# [16,]    2    2    2    2

### Note, by following the "2"s, that this is counting in binary
### from 0 to 2^N - 1, with "1" for 0 and "2" for 1 and least
### significant bit on the left, so it does what is described
### above. But we need to manipulate this, so assign it to K:

K<-hcube(x,scale=1,transl=0)

### Now select only thos which assign unit "1" to Class 1:

K[K[,1]==1,]
#      [,1] [,2] [,3] [,4]
# [1,]    1    1    1    1
# [2,]    1    2    1    1
# [3,]    1    1    2    1
# [4,]    1    2    2    1
# [5,]    1    1    1    2
# [6,]    1    2    1    2
# [7,]    1    1    2    2
# [8,]    1    2    2    2

of which you need to leave off the first, so, finally:

N<-4  ### Or general N at this point

x<-rep(2,N)

K<-hcube(x,scale=1,transl=0)

K[K[,1]==1,][-1,]
#      [,1] [,2] [,3] [,4]
# [1,]    1    2    1    1
# [2,]    1    1    2    1
# [3,]    1    2    2    1
# [4,]    1    1    1    2
# [5,]    1    2    1    2
# [6,]    1    1    2    2
# [7,]    1    2    2    2

That looks like it!

Best wishes,
Ted.

--------------------------------------------------------------------
E-Mail: (Ted Harding) <Ted.Harding at nessie.mcc.ac.uk>
Fax-to-email: +44 (0)870 094 0861
Date: 08-Dec-05                                       Time: 16:19:24
------------------------------ XFMail ------------------------------

______________________________________________
R-help at stat.math.ethz.ch mailing list
https://stat.ethz.ch/mailman/listinfo/r-help