Ales Ziberna
2005-Dec-08 14:45 UTC
[R] Finding all possible partitions of N units into k classes
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.
Thank you in advance for any suggestions.
Best,
Ales Ziberna
Ingmar Visser
2005-Dec-08 16:05 UTC
[R] Finding all possible partitions of N units into k classes
combinations in the gtools package can be helpfull here, best, ingmar> From: "Ales Ziberna" <aleszib at gmail.com> > Date: Thu, 8 Dec 2005 15:45:37 +0100 > To: "R-help" <r-help at stat.math.ethz.ch> > Subject: [R] Finding all possible partitions of N units into k classes > > 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. > > > > Thank you in advance for any suggestions. > > Best, > > Ales Ziberna > > ______________________________________________ > R-help at stat.math.ethz.ch mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html >
(Ted Harding)
2005-Dec-08 16:19 UTC
[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,1which 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 can be readily adapted to do just that (since it initially 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 ------------------------------
Chris Andrews
2005-Dec-09 12:49 UTC
[R] Finding all possible partitions of N units into k classes
nkpartitions <- function(n, k, exact=FALSE, print=FALSE) {
# n objects
# k subgroups
# exactly k or at most k?
# print results as they are found?
if (n != floor(n) | n<=0) stop("n must be positive integer")
if (k != floor(k) | k<=0) stop("k must be positive integer")
if (print) {
printnkp <- function(a) {
for (j in seq(max(a))) cat("{", seq(along=a)[a==j], "}
");
cat("\n")
}
}
# How many?
Stirling2nd <- function(n, k) {
sum((-1)^seq(0,k-1) * choose(k, seq(0,k-1)) * (k-seq(0,k-1))^n) /
factorial(k)
}
rows <- Stirling2nd(n,k)
if (!exact & k>1) {
for (i in seq(k-1,1)) {
rows <- rows + Stirling2nd(n,i)
}
}
if (print) cat("rows =",rows,"\n")
# Allocate space
theparts <- matrix(NA, nrow=rows, ncol=n)
# begin counting
howmany <- 0
# all in one group
a <- rep(1,n)
# does this count?
if (!exact | (k==1)) {
# increase count, store, and print
howmany <- howmany + 1
theparts[howmany,] <- a
if (print) printnkp(a)
}
# search for others
repeat {
# start at high end
last <- n
repeat {
# increment it if possible
if ((a[last] <= max(a[1:(last-1)])) & (a[last] < k)) {
a[last] <- a[last]+1
# does this count?
if (!exact | max(a)==k) {
# increase count, store, and print
howmany <- howmany + 1
theparts[howmany,] <- a
if (print) printnkp(a)
}
# start again at high end.
break
}
# otherwise set to 1 and move to a different object
a[last] <- 1
if (last>2) {
last <- last-1
next
}
# report the partitions
return(theparts)
}
}
}
nkpartitions(5,3)
nkpartitions(5,3,T)
--
Dr Christopher Andrews
University at Buffalo, Department of Biostatistics
242 Farber Hall
candrews at buffalo.edu
716 829 2756