CODEWITHSUNDEEP
ralgorithmcombinationscombinatorics
jlab
jlab

Reputation: 272

Combination with elements never in the same group more than once

There is a group of 14 people. We want to set up a meeting schedule so that all 14 people meet together in groups of 3 (and one group of 2) each week.

However, I do not want any two people in the same group more than once.

For example, if I have a group of c(A,B,C), I do not want a subsequent group to be c(A,B,D), because elements A and B are the same.

The output should be a list, with each element of the list representing a given week. Then within each list element (week) there should be lists of four groups of three people and one group of two people, with each person only appearing once, and between weeks no two persons should appear in the same group.

There are many possible solutions sets for this question. How many weeks we can meet before all combinations have been exhausted? How can I code this in R?

Upvotes: 4

Views: 631

Answers (2)

Rusty Rob
Rusty Rob

Reputation: 17203

Hmm here's a lower bound:

On average each person expects to meets (4*3 + 1*2)/5 = 2.8 people per week

Each person needs to meet 13 people.

13/2.8 = 4.64 weeks. So the answer should be 5 weeks.

Upvotes: 0

dank
dank

Reputation: 333

elements <- c('A','B','C','D','E','F','G','H','I','J','K','L','M','N')
allcomb <- t(combn(elements, 3)) #Returns 364 different combinations

It is possible to filter the ones that have 2 similar letters. However, the answer changes depending on which subgroup you start comparing with. I'm doing it sequentially.(Starting with A,B,C)

for (a in 1:28){
  l <- vector("list", nrow(allcomb))
  for (b in 1:nrow(allcomb)){
    l[[b]] <- sum(allcomb[a,] %in% allcomb[b,])!=2
    }
  allcomb <- allcomb[unlist(l),]
}

Got 28 after trial and error. 

> allcomb
      [,1] [,2] [,3]
 [1,] "A"  "B"  "C" 
 [2,] "A"  "D"  "E" 
 [3,] "A"  "F"  "G" 
 [4,] "A"  "H"  "I" 
 [5,] "A"  "J"  "K" 
 [6,] "A"  "L"  "M" 
 [7,] "B"  "D"  "F" 
 [8,] "B"  "E"  "G" 
 [9,] "B"  "H"  "J" 
[10,] "B"  "I"  "K" 
[11,] "B"  "L"  "N" 
[12,] "C"  "D"  "G" 
[13,] "C"  "E"  "F" 
[14,] "C"  "H"  "K" 
[15,] "C"  "I"  "J" 
[16,] "C"  "M"  "N" 
[17,] "D"  "H"  "L" 
[18,] "D"  "I"  "M" 
[19,] "D"  "J"  "N" 
[20,] "E"  "H"  "M" 
[21,] "E"  "I"  "L" 
[22,] "E"  "K"  "N" 
[23,] "F"  "H"  "N" 
[24,] "F"  "J"  "L" 
[25,] "F"  "K"  "M" 
[26,] "G"  "I"  "N" 
[27,] "G"  "J"  "M" 
[28,] "G"  "K"  "L"

Upvotes: 1

Related Questions