Find all possible team pairing schemes

Question

Feels like this should be straightforward but I have been through stack overflow and combn help, and cannot see solution.

The below players need to be in teams of 3 versus 2. I need to find all possible combinations of teams. For example two possible teams are "Ross", "Bobby" and "Casper" in one team, and "Max" and "Jake" in the other team. How can I code this?

players <- c("Ross", "Bobby", "Max", "Casper", "Jake")

Filmy

FYI, many developers strongly discourage the use of left-to-right assignment in scripts. It makes the assignment action non-obvious, which drastically reduces clarity about the data flow (which variables exist, and what is their current value?) and thus makes code harder to read, debug and modify. – Relax

I use pipes in my code and put assignment on right so everything flows from top to bottom – Filmy

Please have a look at the second-to-last paragraph of this comment explaining why this is a bad idea for code maintainability. – Relax

Answer 1

I think the key step is to randomly choose 3 (or 2) out of 5 players to generate the first team, and the remaining are naturally assigned to the second team.

Probably you can try it like this

combn(players,
  3, 
  function(x) list(team1 = x, team2 = players[!players %in% x]),
  simplify = FALSE
)

or if you don't mind the time efficiency, you can use setdiff instead

combn(players,
    3,
    function(x) list(team1 = x, team2 = setdiff(players, x)),
    simplify = FALSE
  )

and either of which gives

[[1]]
[[1]]$team1
[1] "Ross"  "Bobby" "Max"

[[1]]$team2
[1] "Casper" "Jake"


[[2]]
[[2]]$team1
[1] "Ross"   "Bobby"  "Casper"

[[2]]$team2
[1] "Max"  "Jake"


[[3]]
[[3]]$team1
[1] "Ross"  "Bobby" "Jake"

[[3]]$team2
[1] "Max"    "Casper"


[[4]]
[[4]]$team1
[1] "Ross"   "Max"    "Casper"

[[4]]$team2
[1] "Bobby" "Jake"


[[5]]
[[5]]$team1
[1] "Ross" "Max"  "Jake"

[[5]]$team2
[1] "Bobby"  "Casper"


[[6]]
[[6]]$team1
[1] "Ross"   "Casper" "Jake"

[[6]]$team2
[1] "Bobby" "Max"


[[7]]
[[7]]$team1
[1] "Bobby"  "Max"    "Casper"

[[7]]$team2
[1] "Ross" "Jake"


[[8]]
[[8]]$team1
[1] "Bobby" "Max"   "Jake"

[[8]]$team2
[1] "Ross"   "Casper"


[[9]]
[[9]]$team1
[1] "Bobby"  "Casper" "Jake"

[[9]]$team2
[1] "Ross" "Max"


[[10]]
[[10]]$team1
[1] "Max"    "Casper" "Jake"

[[10]]$team2
[1] "Ross"  "Bobby"

---

Benchmarking

players <- c("Ross", "Bobby", "Max", "Casper", "Jake")

microbenchmark(
  f1 = combn(players,
    3,
    function(x) list(team1 = x, team2 = players[!players %in% x]),
    simplify = FALSE
  ),
  f2 = combn(players,
    3,
    function(x) list(team1 = x, team2 = setdiff(players, x)),
    simplify = FALSE
  )
)

and we will see

Unit: microseconds
 expr    min      lq      mean   median       uq      max neval
   f1 26.200 28.0510  51.55586  29.4515  32.5015 1935.301   100
   f2 97.301 99.8505 119.44610 103.6010 111.1510 1162.501   100

Roubaix

players[!players %in% x]) can be simplified to setdiff(players, x). – Relax

@KonradRudolph yes, I was thinking of setdiff but it would be slow for larger sizes of players or x, so I use %in% instead – Roubaix

Hmm, I don't think it should be slower. Am I wrong? – Relax

@KonradRudolph I added a benchmark – Roubaix

Okay, I did not expect that. Thanks for adding the benchmark. I have to think about why this is happening. – Relax

@KonradRudolph, if you look at setdiff, it is doing a lot more than %in%. In the console, we see setdiff ends up doing u[!duplicated(unclass(u)) & (match(u, v, 0L) == 0L)] whereas %in% simply calls match(x, table, nomatch = 0L) > 0L. – Outbuilding

@JosephWood Yes, I saw that as well. It's definitely not an optimal implementation (match and duplicated will end up doing largely redundant work, and a better implementation would do this work only once). – Relax

Answer 2

There is a function in RcppAlgos (I am the author) called comboGroups built precisely for this task. As of version 2.8.0, we can now handle groups of varying sizes.

library(RcppAlgos)
packageVersion("RcppAlgos")
#> [1] '2.8.0'

We specify the size of each team using the grpSizes parameter:

players <- c("Ross", "Bobby", "Max", "Casper", "Jake")
comboGroups(players, grpSizes = c(2, 3))
#>       Grp1     Grp1     Grp2    Grp2     Grp2    
#>  [1,] "Ross"   "Bobby"  "Max"   "Casper" "Jake"  
#>  [2,] "Ross"   "Max"    "Bobby" "Casper" "Jake"  
#>  [3,] "Ross"   "Casper" "Bobby" "Max"    "Jake"  
#>  [4,] "Ross"   "Jake"   "Bobby" "Max"    "Casper"
#>  [5,] "Bobby"  "Max"    "Ross"  "Casper" "Jake"  
#>  [6,] "Bobby"  "Casper" "Ross"  "Max"    "Jake"  
#>  [7,] "Bobby"  "Jake"   "Ross"  "Max"    "Casper"
#>  [8,] "Max"    "Casper" "Ross"  "Bobby"  "Jake"  
#>  [9,] "Max"    "Jake"   "Ross"  "Bobby"  "Casper"
#> [10,] "Casper" "Jake"   "Ross"  "Bobby"  "Max"

It is very efficient and quite flexible. Let’s test on a larger set of players.

library(microbenchmark)
more_players <- c(players, "Kai", "Eliana", "Jayden", "Luca",
                  "Rowan", "Nova", "Amara", "Finn", "Zion", "Mia")

microbenchmark(
    f1 = combn(more_players,
               7,
               function(x) list(team1 = x, team2 = more_players[!more_players %in% x]),
               simplify = FALSE
    ),
    f2 = combn(more_players,
               7,
               function(x) list(team1 = x, team2 = setdiff(more_players, x)),
               simplify = FALSE
    ),
    f3_rcpp = comboGeneral(
        v = more_players,
        m = 7,
        repetition = FALSE,
        FUN = function(x) list(team1 = x, team2 = more_players[!more_players %in% x])
    ),
    f4 = comboGroups(more_players, grpSizes = c(7, 8)),
    unit = "relative"
)
#> Unit: relative
#>     expr      min       lq     mean   median       uq       max neval  cld
#>       f1 16.22184 19.03265 23.68141 20.78979 26.59770  92.08256   100 a   
#>       f2 41.34947 45.55672 57.30847 54.70320 59.88822 123.09864   100  b  
#>  f3_rcpp 11.83424 14.48575 17.65936 16.24856 21.43574  36.27697   100   c 
#>       f4  1.00000  1.00000  1.00000  1.00000  1.00000   1.00000   100    d

More than 2 Groups

What about more exotic groupings? With most other approaches, efficiency and code maintenance will be an issue.

Say for example, given more_players (15 total players) what if we wanted to find all possible groupings with 2 teams of size 3, one team of size 4, and one team of size 5?

With comboGroups, it is no problem:

system.time(t <- comboGroups(more_players, grpSizes = c(3, 3, 4, 5)))
#>    user  system elapsed 
#>   0.508   0.040   0.548 

head(t, n = 2)
#>      Grp1   Grp1    Grp1  Grp2     Grp2   Grp2  Grp3     Grp3     Grp3   Grp3   
#> [1,] "Ross" "Bobby" "Max" "Casper" "Jake" "Kai" "Eliana" "Jayden" "Luca" "Rowan"
#> [2,] "Ross" "Bobby" "Max" "Casper" "Jake" "Kai" "Eliana" "Jayden" "Luca" "Nova" 
#>      Grp4    Grp4    Grp4   Grp4   Grp4 
#> [1,] "Nova"  "Amara" "Finn" "Zion" "Mia"
#> [2,] "Rowan" "Amara" "Finn" "Zion" "Mia"

tail(t, n = 2)
#>            Grp1    Grp1   Grp1  Grp2   Grp2    Grp2   Grp3   Grp3     Grp3    
#> [6306299,] "Rowan" "Zion" "Mia" "Nova" "Amara" "Finn" "Jake" "Eliana" "Jayden"
#> [6306300,] "Rowan" "Zion" "Mia" "Nova" "Amara" "Finn" "Kai"  "Eliana" "Jayden"
#>            Grp3   Grp4   Grp4    Grp4  Grp4     Grp4  
#> [6306299,] "Luca" "Ross" "Bobby" "Max" "Casper" "Kai" 
#> [6306300,] "Luca" "Ross" "Bobby" "Max" "Casper" "Jake"

If you just need a sample of possible teams, try comboGroupsSample:

comboGroupsSample(
    more_players, grpSizes = c(3, 3, 4, 5), n = 2,
    seed = 42, namedSample = TRUE
)
#>         Grp1    Grp1     Grp1   Grp2    Grp2    Grp2   Grp3   Grp3     Grp3    
#> 3207141 "Bobby" "Jake"   "Mia"  "Luca"  "Amara" "Zion" "Max"  "Casper" "Eliana"
#> 4248729 "Max"   "Casper" "Nova" "Rowan" "Amara" "Finn" "Ross" "Bobby"  "Kai"   
#>         Grp3    Grp4   Grp4     Grp4     Grp4   Grp4  
#> 3207141 "Rowan" "Ross" "Kai"    "Jayden" "Nova" "Finn"
#> 4248729 "Luca"  "Jake" "Eliana" "Jayden" "Zion" "Mia"

Outbuilding

RcppAlgos keeps being better. Nice work! – Rolo

Answer 3

Just to build off @ThomasIsCoding great answer. Further speed could be gained by using the great RcppAlgos library and the comboGeneral function:

players <- c("Ross", "Bobby", "Max", "Casper", "Jake")

microbenchmark(
  f1 = combn(players,
             3,
             function(x) list(team1 = x, team2 = players[!players %in% x]),
             simplify = FALSE
  ),
  f2 = combn(players,
             3,
             function(x) list(team1 = x, team2 = setdiff(players, x)),
             simplify = FALSE
  ),
  f3_rcpp = RcppAlgos::comboGeneral(
    v = players,
    m = 3,
    repetition = FALSE,
    FUN = function(x) list(team1 = x, team2 = players[!players %in% x])
  )
)

BENCHMARK

Unit: microseconds
    expr   min     lq    mean median     uq    max neval
      f1  34.3  37.95  63.693  39.00  41.45 2016.7   100
      f2 143.5 152.40 184.351 155.30 158.95 1961.7   100
 f3_rcpp  29.3  32.40  61.820  33.95  42.40 2205.0   100

Rolo