On Sat, 21 Jun 2008, Gavin Simpson wrote:
Dear Chuck,That is, quite simply, superb! The members of this list never cease to amaze me, and your response is no exception. As an aside, does this type of problem come under a particular name or topic in mathematics?
Yes. Combinatorics. See
http://en.wikipedia.org/wiki/Combinatorics
and/or
http://www.amazon.com/Introductory-Combinatorics-Kenneth-P-Bogart/dp/0121108309/ref=pd_bbs_sr_2?ie=UTF8&s=books&qid=1214082041&sr=8-2
(or any other intro text)
HTH,
Chuck
The ordering need not be exactly as I had it in my example --- that just represented the way I had tried to look at the problem using pen and paper (!) For the record and the archives, the following achieves a slightly different ordering to the one in my example, but which is equally usable for my application; ordered in terms of number of groups.n <- 6 base10 <- seq(0, length=2^(n-1) ) base2.bits <- outer(0:(n-2), base10, function(y,x) ( x %/% (2^y)) %%2 ) res <- sapply(apply( base2.bits==1, 2, which ), function(x) rep(1:(1+length(x)), diff(c(0,x,n)))) ord <- order(apply(res, 2, function(x) length(unique(x)))) res[,ord]And your pointing me to choose(n-1, 0:(n-1)) as the basis to determine the number of possible combinations, allows me to break the result (res[,ord]) down into the chunks I need to work with. Many thanks, Gavin On Sat, 2008-06-21 at 11:30 -0700, Charles C. Berry wrote:On Sat, 21 Jun 2008, Gavin Simpson wrote:Dear List, I have a problem I'm finding it difficult to make headway with. Say I have 6 ordered observations, and I want to find all combinations of splitting these 6 ordered observations in g groups, where g = 1, ..., 6. Groups can only be formed by adjacent observations, so observations 1 and 4 can't be in a group on their own, only if 1,2,3&4 are all in the group.Right. And in the example below there are 32 distinct patterns. Which arises from sum( choose( 5, 0:5 ) ) different placements of 0:5 split positions. You can represent the splits as a binary number with n-1 bits: 00000 implies no splits, 10000 implies a split between 1 and 2, 10100 implies splits between 1 and 2 and between 3 and 4, et cetera. So, 32 arises as 2^5, too. Something like this:base10 <- seq(0, length=2^(n-1) ) base2.bits <- outer(0:(n-2), base10, function(y,x) ( x %/% (2^y)) %%2 ) sapply(apply( base2.bits==1, 2, which ), function(x) rep(1:(1+length(x)), diff(c(0,x,n))))Getting this in the same column order as your example is left as an exercise for the reader. HTH, ChuckFor example, with 6 observations, the columns of the matrices below represent the groups that can be formed by placing the 6 ordered observations into 2-5 groups. Think of the columns of these matrices as being an indicator of group membership. We then cbind these matrices with the trivial partitions into 1 and 6 groups: mat2g <- matrix(c(1,1,1,1,1, 2,1,1,1,1, 2,2,1,1,1, 2,2,2,1,1, 2,2,2,2,1, 2,2,2,2,2), nrow = 6, ncol = 5, byrow = TRUE) mat3g <- matrix(c(1,1,1,1,1,1,1,1,1,1, 2,2,2,2,1,1,1,1,1,1, 3,2,2,2,2,2,2,1,1,1, 3,3,2,2,3,2,2,2,2,1, 3,3,3,2,3,3,2,3,2,2, 3,3,3,3,3,3,3,3,3,3), nrow = 6, ncol = 10, byrow = TRUE) mat4g <- matrix(c(1,1,1,1,1,1,1,1,1,1, 2,2,2,2,2,2,1,1,1,1, 3,3,3,2,2,2,2,2,2,1, 4,3,3,3,3,2,3,3,2,2, 4,4,3,4,3,3,4,3,3,3, 4,4,4,4,4,4,4,4,4,4), nrow = 6, ncol = 10, byrow = TRUE) mat5g <- matrix(c(1,1,1,1,1, 2,2,2,2,1, 3,3,3,2,2, 4,4,3,3,3, 5,4,4,4,4, 5,5,5,5,5), nrow = 6, ncol = 5, byrow = TRUE) cbind(rep(1,6), mat2g, mat3g, mat4g, mat5g, 1:6) I'd like to be able to do this automagically, for any (reasonable, small, say n = 10-20) number of observations, n, and for g = 1, ..., n groups. I can't see the pattern here or a way forward. Can anyone suggest an approach? Thanks in advance, Gavin -- %~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~% Dr. Gavin Simpson [t] +44 (0)20 7679 0522 ECRC, UCL Geography, [f] +44 (0)20 7679 0565 Pearson Building, [e] gavin.simpsonATNOSPAMucl.ac.uk Gower Street, London [w] http://www.ucl.ac.uk/~ucfagls/ UK. WC1E 6BT. [w] http://www.freshwaters.org.uk %~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~% ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.Charles C. Berry (858) 534-2098 Dept of Family/Preventive Medicine E mailto:[EMAIL PROTECTED] UC San Diego http://famprevmed.ucsd.edu/faculty/cberry/ La Jolla, San Diego 92093-0901-- %~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~% Dr. Gavin Simpson [t] +44 (0)20 7679 0522 ECRC, UCL Geography, [f] +44 (0)20 7679 0565 Pearson Building, [e] gavin.simpsonATNOSPAMucl.ac.uk Gower Street, London [w] http://www.ucl.ac.uk/~ucfagls/ UK. WC1E 6BT. [w] http://www.freshwaters.org.uk %~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~% ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Charles C. Berry (858) 534-2098
Dept of Family/Preventive Medicine
E mailto:[EMAIL PROTECTED] UC San Diego
http://famprevmed.ucsd.edu/faculty/cberry/ La Jolla, San Diego 92093-0901
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
