[R] Generating groupings of ordered observations

[Gavin Simpson]

On Sat, 2008-06-21 at 17:56 -0400, Gabor Grothendieck 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.
> >
<snip />
> >
> > 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):

Thanks for this Gabor. Will take a look.

One additional complication that I failed to mention, is that I would
like to state the number of groups. So in my example, instead of
splitting the 6 observations into 1,2,...,6 groups, I would like to get
only the sets that partition the 6 observations into say 4 groups.

For larger problems, where n is > 100 it is not possible to do the
required calculations on the choose(n-1, 0:(n-1)) possible combinations.
Instead we would evaluate the combinations of the n observations
relating to a small number of groups, say g = 1:10 where n = 100 for
example.

So Chuck and your solutions answer the question I asked, but I can't see
how to modify them to set the number of groups to be less than the
number of observations.

All the best,

G

> 
> > 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
-- 
%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%
 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
%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%~%