R help - Mar 2007 - enumerating non-overlapping pairs of elements from a vector

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.

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