[R] enumerating non-overlapping pairs of elements from a vector

[Robin Hankin]

Allan

the general problem you refer to is "set partitions", although
I'm not clear whether the order of the sets themselves
makes a  difference (we in the enumerative combinatorics
world refer to "indistinguishable boxes").

Your application would be set partitions with a specific shape,
in this case 2,2,2,...,2,2,1  or 2,2,2,,,,,2.

I am working on a generalization of your problem Right Now,
and hope to have a complete solution ready within a couple
of months (but then again I've been saying this for a long time
now ;-)


What's your application?


best wishes

Robin


On 5 Mar 2007, at 14:56, Allan Strand wrote:

> Hi All,
>
> I'm trying to come up with a clear and concise (and fast?) solution to
> the following problem.
>
> I would like to take a vector 'v' and enumerate all of the ways in
> which it can be broken into n sets of length 2 (if the length of the
> vector is odd, and an additional set of length 1).  An element of 'v'
> can
> only appear in one set. Order within sets is not important.  Vector
> 'v' can be of lengths 2-12
>
>  'n' is determined by length(v)%/%2
>  if length(v)%%2 is non-zero, the additional set of length 1 is used
>
> For example vector 'v':
> v = (1,2,3,4)
>
> The solution would be (rows are combinations of sets chosen, where
> each element only appears once)
>
> 1 2, 3 4
> 1 3, 2 4
> 1 4, 2 3
>
> In the case where length(v) is odd
> v = (1,2,3,4,5)
> 1 2, 3 4, 5
> 1 3, 2 4, 5
> 1 4, 2 3, 5
> 5 2, 3 4, 1
> 5 3, 2 4, 1
> 5 4, 2 3, 1
> 5 1, 3 4, 2
> 5 3, 1 4, 2
> 5 4, 1 3, 2
> and so on...
>
> Certainly pulling all combinations of two or one elements is not a big
> deal, for example
>
> combinations(5,2,c(1,2,3,4,5),repeats.allowed=T)
>
> from the 'gtools' package would do something like this.
>
> I'm stuck on a clean solution for enumerating all the non-overlapping
> sets without some elaborate looping and checking scheme.  No doubt
> this is a lapse in my understanding of combinatorics.  Any help would
> be greatly appreciated
>
> cheers,
> a.
>
> ______________________________________________
> 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
> and provide commented, minimal, self-contained, reproducible code.

--
Robin Hankin
Uncertainty Analyst
National Oceanography Centre, Southampton
European Way, Southampton SO14 3ZH, UK
  tel  023-8059-7743