title: All combinations to split a vector into two groups in R
body: <p>I am trying to figure out an efficient way to obtain all unique combinations that elements in a vector (the vector is always a sequence between 1:n) can be split into two equal-sized groups. Each element in the vector must be represented once (in one of the two groups). For example, when n = 6, the vector will be [1,2,3,4,5,6]. This can be split into ten unique ways to form two equal-sized groups:</p>
  
  <pre><code>123 | 456
  124 | 356
  125 | 346
  126 | 345
  134 | 256
  135 | 246
  136 | 245
  145 | 236
  146 | 235
  156 | 234
  </code></pre>
  
  <p>Note that the order of the values <em>within</em> the groups does not matter, so:</p>
  
  <pre><code>156 | 234
  </code></pre>
  
  <p>is the same as:</p>
  
  <pre><code>651 | 342
  </code></pre>
  
  <p>Also note that symmetrical solutions do not matter either, so:</p>
  
  <pre><code>156 | 234
  </code></pre>
  
  <p>is the same as:</p>
  
  <pre><code>234 | 156
  </code></pre>
  
  <p>When n = 4, there are 3 solutions. When n = 6, there are 10 solutions. When n = 8, there are 35 solutions. I believe I came up with a way to obtain these solutions in R. However, it is a bit slow once n becomes larger. For the most part, I am satisfied with what I have, but want to ask if anyone has suggestions on ways to improve its speed or code quality etc. In particular, I begin with a solution where there are lots of repeats, and then I delete repeats. This, I think, makes the algorithm rather slow.</p>
  
  <pre><code>library(combinat)
  # Number of elements in array
  n = 6
  # Array
  dat &lt;- 1:n
  
  # All possible permutations for array
  ans &lt;- permn(dat)
  lengthAns &lt;- length(ans)
  ansDF &lt;- data.frame()
  # Place first permutation in final answer data frame
  ansDF &lt;- rbind(ansDF, ans[[1]])
  
  # Look at the rest of the possible permutations. Determine for each one if it is truly unique from all the previously-listed possible permutations. If it is unique from them, then add it to the final answer data frame
  for (i in 2:lengthAns){
    j = i
    k = TRUE
    while (k &amp;&amp; j &gt; 1){
      j = j-1
      if(setequal(ans[[i]][1:(n/2)], ans[[j]][1:(n/2)]))
        k = FALSE
      if(setequal(ans[[i]][1:(n/2)], ans[[j]][(n/2+1):(n)]))
        k = FALSE
    }
    if (k){
      ansDF &lt;- rbind(ansDF, ans[[i]])
    }
  }
  
  # At this point, ansDF contains all unique possible ways to split the array into two-equally sized groups.
  </code></pre>