CODEWITHSUNDEEP
ralgorithmcombinationspermutation
user1830307
user1830307

Reputation:

All combinations to split a vector into two groups in R

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 within the groups does not matter, so:

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.

Upvotes: 2

Views: 1585

Answers (1)

dww
dww

Reputation: 31454

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

Upvotes: 3

Related Questions