LanneR - 5 months ago 22

R Question

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:

`123 | 456`

124 | 356

125 | 346

126 | 345

134 | 256

135 | 246

136 | 245

145 | 236

146 | 235

156 | 234

Note that the order of the values

`156 | 234`

is the same as:

`651 | 342`

Also note that symmetrical solutions do not matter either, so:

`156 | 234`

is the same as:

`234 | 156`

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.

`library(combinat)`

# Number of elements in array

n = 6

# Array

dat <- 1:n

# All possible permutations for array

ans <- permn(dat)

lengthAns <- length(ans)

ansDF <- data.frame()

# Place first permutation in final answer data frame

ansDF <- 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 && j > 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 <- rbind(ansDF, ans[[i]])

}

}

# At this point, ansDF contains all unique possible ways to split the array into two-equally sized groups.

Answer

```
N = 6
x = 1:N
x1 = combn(x, N/2) #how many ways can we take half the elements to form the 1st group
NC = NCOL(x1)
x2 = x1[, NC:1] # simplified way to generate the complementary groups that include values not in x1
grp1 = t(x1[,1:(NC/2)]) # We only need half of the rows, the 2nd half containing the same set in reverse order
grp2 = t(x2[,1:(NC/2)])
all.comb = cbind(grp1, grp2)
# [,1] [,2] [,3] [,4] [,5] [,6]
# [1,] 1 2 3 4 5 6
# [2,] 1 2 4 3 5 6
# [3,] 1 2 5 3 4 6
# [4,] 1 2 6 3 4 5
# [5,] 1 3 4 2 5 6
# [6,] 1 3 5 2 4 6
# [7,] 1 3 6 2 4 5
# [8,] 1 4 5 2 3 6
# [9,] 1 4 6 2 3 5
#[10,] 1 5 6 2 3 4
```