在 R 中找到所有可能的团队

Question

感觉这应该是直截了当的，但我已经经历了堆栈溢出和

combn

帮助，但看不到解决方案。

以下玩家需要组成 3 对 2 的队伍。我需要找到所有可能的队伍组合。例如，两个可能的团队是一个团队中的“Ross”、“Bobby”和“Casper”，以及另一个团队中的“Max”和“Jake”。我该如何编码？

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

Answer 1

我觉得最关键的一步是从5个玩家中随机选择3（或2）个生成第一队，剩下的自然分配到第二队

或许你可以这样试试

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

或者不介意时间效率的话，可以用

setdiff

代替

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

其中任何一个给出

[[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"

---

基准测试

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
  )
)

我们会看到

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

Answer 2

只是为了建立@ThomasIsCoding 很好的答案。通过使用强大的 RcppAlgos 库和

comboGeneral

函数可以获得进一步的速度：

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])
  )
)

基准

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

Answer 3

RcppAlgos

（我是作者）中有一个名为

comboGroups

的函数正是为这个任务而构建的。目前它只能从 GitHub 存储库中获得，但是它将在下一个版本中发布到 CRAN。

首先我们从 GitHub 安装开发版本：

devtools::install_github("jwood000/RcppAlgos", ref = "partition_any_size")
#> Downloading GitHub repo jwood000/RcppAlgos@partition_any_size
.
.
.
#> ** checking absolute paths in shared objects and dynamic libraries
#> ** testing if installed package can be loaded from final location
#> ** testing if installed package keeps a record of temporary installation path
#> * DONE (RcppAlgos)

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

现在，我们打电话给

comboGroups

。我们使用

grpSizes

参数指定每个团队的规模：

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"

效率很高，也很灵活。让我们测试更多的玩家。

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

microbenchmark(
    f1 = combn(players,
               7,
               function(x) list(team1 = x, team2 = players[!players %in% x]),
               simplify = FALSE
    ),
    f2 = combn(players,
               7,
               function(x) list(team1 = x, team2 = setdiff(players, x)),
               simplify = FALSE
    ),
    f3_rcpp = comboGeneral(
        v = players,
        m = 7,
        repetition = FALSE,
        FUN = function(x) list(team1 = x, team2 = players[!players %in% x])
    ),
    f4 = comboGroups(players, grpSizes = c(7, 8)),
    unit = "relative"
)
#> Warning in microbenchmark(f1 = combn(players, 7, function(x) list(team1 = x, :
#> less accurate nanosecond times to avoid potential integer overflows
#> Unit: relative
#>     expr      min       lq     mean   median       uq       max neval
#>       f1 16.16546 20.01651 25.68449 23.83618 26.54028  85.11562   100
#>       f2 43.59662 47.74038 58.89298 55.63955 63.31305 115.75674   100
#>  f3_rcpp 11.59484 14.64660 19.07359 16.67879 20.29973  91.36375   100
#>       f4  1.00000  1.00000  1.00000  1.00000  1.00000   1.00000   100