[R] Generating groupings of ordered observations

[Gabor Grothendieck]

I meant 0:31, not 0:15.

On Sat, Jun 21, 2008 at 5:56 PM, Gabor Grothendieck
<ggrothendieck at gmail.com> wrote:
> On Sat, Jun 21, 2008 at 12:40 PM, Gavin Simpson <gavin.simpson at ucl.ac.uk> 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.
>>
>> For 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?
>>
>
> Peter Wolf has APL-style encode/decode functions on his web site that
> can readily be used for this.  The output of the encode below are the binary
> digits expansions of the numbers 0:15, one per column, and the remainder
> transforms that matrix to the required one (but columns are in a different
> order than yours):
>
>> source("http://www.wiwi.uni-bielefeld.de/~wolf/software/R-wtools/decodeencode/decodeencode.R")
>> n <- 6
>> n1 <- n-1
>> apply(rbind(1, encode(0:(2^n1-1), rep(2, n1))), 2, cumsum)
>     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
> [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23]
> [,24] [,25] [,26]
> [1,]    1    1    1    1    1    1    1    1    1     1     1     1
>  1     1     1     1     1     1     1     1     1     1     1     1
>  1     1
> [2,]    1    1    1    1    1    1    1    1    1     1     1     1
>  1     1     1     1     2     2     2     2     2     2     2     2
>  2     2
> [3,]    1    1    1    1    1    1    1    1    2     2     2     2
>  2     2     2     2     2     2     2     2     2     2     2     2
>  3     3
> [4,]    1    1    1    1    2    2    2    2    2     2     2     2
>  3     3     3     3     2     2     2     2     3     3     3     3
>  3     3
> [5,]    1    1    2    2    2    2    3    3    2     2     3     3
>  3     3     4     4     2     2     3     3     3     3     4     4
>  3     3
> [6,]    1    2    2    3    2    3    3    4    2     3     3     4
>  3     4     4     5     2     3     3     4     3     4     4     5
>  3     4
>     [,27] [,28] [,29] [,30] [,31] [,32]
> [1,]     1     1     1     1     1     1
> [2,]     2     2     2     2     2     2
> [3,]     3     3     3     3     3     3
> [4,]     3     3     4     4     4     4
> [5,]     4     4     4     4     5     5
> [6,]     4     5     4     5     5     6
>