如何从n个对象中生成r个对象的序列？我正在寻找一种进行排列或组合的方法，包括/不包括替换，具有不同和非不同的项目（也称为多重集）。
这与twelvefold way相关。 “不同”的解决方案可以包含在twelvefold way中，而“非不同”的解决方案则不包含在内。
这与twelvefold way相关。 “不同”的解决方案可以包含在twelvefold way中，而“非不同”的解决方案则不包含在内。
如何在R中生成对象的排列或组合？
35
- Randy Lai
5
3有争议地说，这种类型的问题有十二个问题。 - Josh O'Brien
是的，这是一种非常有用的方式来组织和思考所有这些不同的组合对象。顺便说一下，大多数谷歌搜索“十二重方式”得到的第一页结果都包括比我链接的维基百科页面更易读的表格/更清晰的解释。 - Josh O'Brien
谢谢提供的信息。我想我缺少的是满射情况。对吗？【更新】：看起来好像不对。 - Randy Lai
2你说得对，那是错的 ;) 12折分类基于的特征与你选择的特征有所不同。对我来说，最好的思考方式是将n个球放入m个瓮中。它们可以被放置在三种可能的限制下（无限制、必须是单射或必须是满射），并且有4种标记/未标记的球和瓮的组合。这里和这里是两个使用该方法来看待问题的来源。 - Josh O'Brien
最后，我弄清了这里8个问题和twelvefold之间的区别。这里的四个问题在twelvefold中（那些“不同”的问题），而那些“非不同”的问题不在twelvefold中。 - Randy Lai
3个回答
41
在R中走过组合数学的一部分
下面，我们将研究能够生成组合和排列的软件包。如果我遗漏了任何软件包，请原谅我，并请留下评论或更好的是编辑此帖。
分析大纲：
- 介绍
- 设置
- 组合
- 排列
- 多重集合
- 总结
- 内存
在开始之前，我们注意到具有替换的不同/非不同项目选择的组合/排列与m次等效。这是因为当我们进行替换时，它并不是特定的。因此，无论特定元素最初出现了多少次，输出都将重复该元素的实例1至m次。
1. 介绍
软件包：
gtoolscombinatmulticoolpartitionsRcppAlgosarrangementsutils
我没有包括permute或permutations，因为它们并不真正用于解决这些类型的问题。我也没有包括更新的gRbase，因为某些情况会导致我的计算机崩溃。
|————————————— 概述 —————————————-|
|_________________| gtools | combinat | multicool | partitions |
| comb rep | Yes | | | |
| comb NO rep | Yes | Yes | | |
| perm rep | Yes | | | |
| perm NO rep | Yes | Yes | Yes | Yes |
| perm multiset | | | Yes | Yes |
| comb multiset | | | | |
| accepts factors | | Yes | | |
| m at a time | Yes | Yes/No | | |
| general vector | Yes | Yes | Yes | |
| iterable | | | Yes | |
| parallelizable | | | | |
| multi-threaded | | | | |
| big integer | | | | |
|_________________| arrangements | RcppAlgos | utils |
| comb rep | Yes | Yes | |
| comb NO rep | Yes | Yes | Yes |
| perm rep | Yes | Yes | |
| perm NO rep | Yes | Yes | |
| perm multiset | Yes | Yes | |
| comb multiset | Yes | Yes | |
| accepts factors | Yes | Yes | Yes |
| m at a time | Yes | Yes | Yes |
| general vector | Yes | Yes | Yes |
| iterable | Yes | Yes | |
| parallelizable | Yes | Yes | |
| big integer | Yes | Yes | |
| multi-threaded | | Yes | |
任务中的“
m at a time”和“general vector”指的是生成“每次m个结果”和重新排列“通用向量”的能力，而不是1:n。 在实践中，我们通常关心的是找到一般向量的重新排列，因此尽可能时，下面的所有考试都将反映这一点。
2. 设置
所有基准测试均在3个不同的设置上运行。
- 2022年Macbook Air苹果M2 24 GB
- 2020年Macbook Pro i7 16 GB
- 2022年Windows Surface i5 16 GB
library(microbenchmark)
## print up to 4 digits to keep microbenchmark output tidy
options(digits = 4)
options(width = 90)
numThreads <- min(as.integer(RcppAlgos::stdThreadMax() / 2), 6)
numThreads
#> [1] 4
pkgs <- c("gtools", "combinat", "multicool", "partitions",
"RcppAlgos", "arrangements", "utils", "microbenchmark")
sapply(pkgs, packageVersion, simplify = FALSE)
#> $gtools
#> [1] '3.9.3'
#>
#> $combinat
#> [1] '0.0.8'
#>
#> $multicool
#> [1] '0.1.12'
#>
#> $partitions
#> [1] '1.10.7'
#>
#> $RcppAlgos
#> [1] '2.6.0'
#>
#> $arrangements
#> [1] '1.1.9'
#>
#> $utils
#> [1] '4.2.1'
#>
#> $microbenchmark
#> [1] '1.4.7'
以下结果是从设置#1（即Macbook Air M2）获得的。在Macbook Pro上的结果类似，但在Windows设置中，多线程效果不太明显。在Windows设置中，有时串行执行更快。我们将使用模式
package::function调用所有函数，因此不需要library调用。
3. 组合
首先，我们研究选择m个不重复元素的组合。
RcppAlgoscombinatgtoolsarrangementsutils
如何实现：
set.seed(13)
tVec1 <- sort(sample(100, 20))
m <- 10
t1 <- RcppAlgos::comboGeneral(tVec1, m) ## returns matrix with m columns
t3 <- combinat::combn(tVec1, m) ## returns matrix with m rows
t4 <- gtools::combinations(20, m, tVec1) ## returns matrix with m columns
identical(t(t3), t4) ## must transpose to compare
#> [1] TRUE
t5 <- arrangements::combinations(tVec1, m)
identical(t1, t5)
#> [1] TRUE
t6 <- utils::combn(tVec1, m) ## returns matrix with m rows
identical(t(t6), t4) ## must transpose to compare
#> [1] TRUE
基准测试：
microbenchmark(
cbRcppAlgosPar = RcppAlgos::comboGeneral(tVec1, m,
nThreads = numThreads),
cbRcppAlgosSer = RcppAlgos::comboGeneral(tVec1, m),
cbGtools = gtools::combinations(20, m, tVec1),
cbCombinat = combinat::combn(tVec1, m),
cbUtils = utils::combn(tVec1, m),
cbArrangements = arrangements::combinations(tVec1, m),
unit = "relative"
)
#> Warning in microbenchmark(cbRcppAlgosPar = RcppAlgos::comboGeneral(tVec1, : less accurate
#> nanosecond times to avoid potential integer overflows
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.0000 100
#> cbRcppAlgosSer 2.712 2.599 1.280 2.497 2.477 0.2666 100
#> cbGtools 739.325 686.803 271.623 679.894 661.560 11.7178 100
#> cbCombinat 173.836 166.265 76.735 176.052 191.945 4.9075 100
#> cbUtils 179.895 170.345 71.639 169.661 178.385 3.8900 100
#> cbArrangements 2.717 2.995 1.975 2.835 2.935 0.8195 100
现在，我们来考虑每次选择带有替换的m种组合。
RcppAlgosgtoolsarrangements
set.seed(97)
tVec2 <- sort(rnorm(12))
m <- 9
t1 <- RcppAlgos::comboGeneral(tVec2, m, repetition = TRUE)
t3 <- gtools::combinations(12, m, tVec2, repeats.allowed = TRUE)
identical(t1, t3)
#> [1] TRUE
t4 <- arrangements::combinations(tVec2, m, replace = TRUE)
identical(t1, t4)
#> [1] TRUE
基准测试：
microbenchmark(
cbRcppAlgosPar = RcppAlgos::comboGeneral(tVec2, m, TRUE,
nThreads = numThreads),
cbRcppAlgosSer = RcppAlgos::comboGeneral(tVec2, m, TRUE),
cbGtools = gtools::combinations(12, m, tVec2, repeats.allowed = TRUE),
cbArrangements = arrangements::combinations(tVec2, m, replace = TRUE),
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.0000 1.000 1.0000 1.0000 100
#> cbRcppAlgosSer 1.987 2.382 0.9173 2.347 1.2776 0.9733 100
#> cbGtools 670.126 517.561 103.8726 523.135 177.0940 12.0440 100
#> cbArrangements 2.300 2.582 0.8294 2.542 0.9212 1.0089 100
4. 排列组合
首先，我们来研究选取 m 个不同元素的排列。
RcppAlgosgtoolsarrangements
操作方法：
tVec3 <- as.integer(c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29))
t1 <- RcppAlgos::permuteGeneral(tVec3, 6)
t3 <- gtools::permutations(10, 6, tVec3)
identical(t1, t3)
#> [1] TRUE
t4 <- arrangements::permutations(tVec3, 6)
identical(t1, t4)
#> [1] TRUE
基准测试：
microbenchmark(
cbRcppAlgosPar = RcppAlgos::permuteGeneral(tVec3, 6,
nThreads = numThreads),
cbRcppAlgosSer = RcppAlgos::permuteGeneral(tVec3, 6),
cbGtools = gtools::permutations(10, 6, tVec3),
cbArrangements = arrangements::permutations(tVec3, 6),
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.0000 100
#> cbRcppAlgosSer 1.204 1.553 1.522 1.523 1.509 0.5722 100
#> cbGtools 357.078 308.978 288.396 301.611 292.862 64.8564 100
#> cbArrangements 2.356 2.361 2.183 2.292 2.224 0.4605 100
下面，我们将研究使用一般向量进行无重复排列的所有排列。
以下是一些可用于此目的的R包：
RcppAlgosgtoolscombinatmulticoolarrangements
tVec3Prime <- tVec3[1:9]
## For RcppAlgos, arrangements, & gtools (see above)
t4 <- combinat::permn(tVec3Prime) ## returns a list of vectors
## convert to a matrix
t4 <- do.call(rbind, t4)
t5 <- multicool::allPerm(multicool::initMC(tVec3Prime)) ## returns a matrix with n columns
all.equal(t4[do.call(order,as.data.frame(t4)),],
t5[do.call(order,as.data.frame(t5)),])
#> [1] TRUE
基准测试：
microbenchmark(
cbRcppAlgosPar = RcppAlgos::permuteGeneral(tVec3Prime,
nThreads = numThreads),
cbRcppAlgosSer = RcppAlgos::permuteGeneral(tVec3Prime),
cbGtools = gtools::permutations(9, 9, tVec3Prime),
cbCombinat = combinat::permn(tVec3Prime),
cbMulticool = multicool::allPerm(multicool::initMC(tVec3Prime)),
cbArrangements = arrangements::permutations(tVec3Prime),
times = 25,
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.0 25
#> cbRcppAlgosSer 1.555 2.187 2.616 2.190 2.274 10.3 25
#> cbGtools 1913.125 1850.589 1893.918 1877.707 1915.601 2124.5 25
#> cbCombinat 508.360 512.182 562.042 532.123 595.722 715.3 25
#> cbMulticool 103.061 103.694 128.480 118.169 127.118 208.3 25
#> cbArrangements 3.216 3.583 13.566 3.544 3.561 139.2 25
现在，我们要考虑没有替换的排列，对于
1:n（返回所有排列）。
RcppAlgosgtoolscombinatmulticoolpartitionsarrangements
t1 <- partitions::perms(9) ## returns an object of type 'partition' with n rows
identical(t(as.matrix(t1)), RcppAlgos::permuteGeneral(9))
#> [1] TRUE
基准测试:
microbenchmark(
cbRcppAlgosPar = RcppAlgos::permuteGeneral(9, nThreads = numThreads),
cbRcppAlgosSer = RcppAlgos::permuteGeneral(9),
cbGtools = gtools::permutations(9, 9),
cbCombinat = combinat::permn(9),
cbMulticool = multicool::allPerm(multicool::initMC(1:9)),
cbPartitions = partitions::perms(9),
cbArrangements = arrangements::permutations(9),
times = 25,
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 25
#> cbRcppAlgosSer 1.583 2.218 2.587 2.261 2.591 1.814 25
#> cbGtools 2010.303 1855.443 1266.853 1898.458 1903.055 217.422 25
#> cbCombinat 511.196 515.197 392.252 533.737 652.125 86.305 25
#> cbMulticool 108.152 103.188 80.469 108.227 120.804 23.504 25
#> cbPartitions 6.139 6.018 7.167 5.993 6.403 9.446 25
#> cbArrangements 4.089 3.797 3.135 3.791 3.760 1.858 25
最后，我们来看一下带有替换的排列。
RcppAlgosgtoolsarrangements
如何操作：
t1 <- RcppAlgos::permuteGeneral(tVec3, 5, repetition = TRUE)
t3 <- gtools::permutations(10, 5, tVec3, repeats.allowed = TRUE)
t4 <- arrangements::permutations(x = tVec3, k = 5, replace = TRUE)
identical(t1, t3)
#> [1] TRUE
identical(t1, t4)
#> [1] TRUE
这个新的基准测试结果有些出人意料，考虑到之前的结果。
microbenchmark(
cbRcppAlgosPar = RcppAlgos::permuteGeneral(
tVec3, 5, TRUE, nThreads = numThreads
),
cbRcppAlgosSer = RcppAlgos::permuteGeneral(tVec3, 5, TRUE),
cbGtools = gtools::permutations(10, 5, tVec3, repeats.allowed = TRUE),
cbArrangements = arrangements::permutations(tVec3, 5, replace = TRUE),
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 100
#> cbRcppAlgosSer 1.307 1.669 1.465 1.561 1.513 1.015 100
#> cbGtools 6.364 6.188 5.448 5.762 5.434 1.625 100
#> cbArrangements 2.584 2.442 1.824 2.265 2.135 0.117 100
这不是笔误……gtools::permutations 几乎和其他编译函数一样快。我鼓励读者去查看 gtools::permutations 的源代码，因为它展示了最优雅的编程之一（无论是在 R 中还是其他语言中）。
5. 多重集合
首先，我们研究多重集合的组合。
RcppAlgosarrangements
要找到多重集合的组合/排列，使用 RcppAlgos 的 freqs 参数来指定源向量 v 中每个元素重复的次数。
set.seed(496)
myFreqs <- sample(1:5, 12, replace = TRUE)
## This is how many times each element will be repeated
tVec4 <- as.integer(c(1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233))
t1 <- RcppAlgos::comboGeneral(tVec4, 12, freqs = myFreqs)
t3 <- arrangements::combinations(tVec4, 12, freq = myFreqs)
identical(t1, t3)
#> [1] TRUE
基准测试：
microbenchmark(
cbRcppAlgosPar = RcppAlgos::comboGeneral(
tVec4, 12, freqs = myFreqs, nThreads = numThreads
),
cbRcppAlgosSer = RcppAlgos::comboGeneral(tVec4, 12, freqs = myFreqs),
cbArrangements = arrangements::combinations(tVec4, 12, freq = myFreqs),
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.0000 100
#> cbRcppAlgosSer 3.197 3.012 2.003 2.831 2.681 0.1658 100
#> cbArrangements 9.391 7.830 4.901 7.252 6.731 0.3140 100
对于每次选择m个多重集合的排列，我们有以下两种方法：
RcppAlgosarrangements
操作步骤：
set.seed(123)
tVec5 <- sort(runif(5))
t1 <- RcppAlgos::permuteGeneral(tVec5, 8, freqs = rep(4, 5))
t3 <- arrangements::permutations(tVec5, 8, freq = rep(4, 5))
identical(t1, t3)
#> [1] TRUE
基准测试：
microbenchmark(
cbRcppAlgosPar = RcppAlgos::permuteGeneral(
tVec5, 8, freqs = rep(4, 5), nThreads = numThreads
),
cbRcppAlgosSer = RcppAlgos::permuteGeneral(tVec5, 8, freqs = rep(4, 5)),
cbArrangements = arrangements::permutations(tVec5, 8, freq = rep(4, 5)),
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 100
#> cbRcppAlgosSer 3.336 3.326 2.990 3.330 3.517 2.106 100
#> cbArrangements 3.751 3.746 3.346 3.757 3.840 2.305 100
对于返回所有排列的多重集排列，我们有以下几种方法：
RcppAlgosmulticoolpartitionsarrangements
操作步骤：
tVec6 <- (1:5)^3
## For multicool, you must have the elements explicitly repeated
tVec6Prime <- rep(tVec6, times = rep(2, 5))
## for comparison
t1 <- RcppAlgos::permuteGeneral(tVec6, freqs = rep(2, 5))
t2 <- partitions::multiset(tVec6Prime)
t3 <- multicool::allPerm(multicool::initMC(tVec6Prime))
t4 <- arrangements::permutations(tVec6, freq = rep(2, 5))
## the package partitions, returns class of integer
## whereas RcppAlgos preserves class of tVec6 (i.e. numeric)
all.equal(t1, t(as.matrix(t2)))
#> [1] TRUE
identical(t1[do.call(order,as.data.frame(t1)),],
t3[do.call(order,as.data.frame(t3)),])
#> [1] TRUE
identical(t1, t4)
#> [1] TRUE
基准测试：
microbenchmark(
cbRcppAlgosPar = RcppAlgos::permuteGeneral(
tVec6, freqs = rep(2, 5), nThreads = numThreads
),
cbRcppAlgosSer = RcppAlgos::permuteGeneral(tVec6, freqs = rep(2, 5)),
cbMulticool = multicool::allPerm(multicool::initMC(tVec6Prime)),
cbPartitions = partitions::multiset(tVec6Prime),
cbArrangements = arrangements::permutations(tVec6, freq = rep(2, 5)),
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.0000 100
#> cbRcppAlgosSer 2.485 2.141 2.289 2.584 2.511 1.0250 100
#> cbMulticool 80.195 66.237 45.540 64.971 66.057 3.5655 100
#> cbPartitions 5.731 4.786 3.925 4.719 4.953 0.4558 100
#> cbArrangements 2.999 2.907 3.270 2.966 2.906 3.1214 100
6. 总结
gtools 和 combinat 都是用于重新排列向量元素的成熟软件包。使用 gtools 可以得到更多选项（请参见上面的概述），而使用 combinat 可以重新排列factors。使用 multicool，可以重新排列多重集合。虽然本问题中 partitions 功能有限，但该软件包具备高效处理整数分割的强大功能。
arrangements
- 按字典顺序输出结果。
- 允许用户通过
layout参数指定格式（“row：行主要”，“colmnn：列主要”和“list：列表”）。 - 提供方便的方法，如使用迭代器时的
collect和getnext。 - 通过
getnext可以生成超过2^31 - 1种组合/排列方式。注意：RcppAlgos（通过nextItem）和multicool（通过nextPerm）也能够实现此功能。 - 支持 GMP，可以探索具有许多结果的向量的组合/排列。
注意：
icomb <- arrangements::icombinations(1000, 7)
icomb$getnext()
#> [1] 1 2 3 4 5 6 7
icomb$getnext(d = 5)
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,] 1 2 3 4 5 6 8
#> [2,] 1 2 3 4 5 6 9
#> [3,] 1 2 3 4 5 6 10
#> [4,] 1 2 3 4 5 6 11
#> [5,] 1 2 3 4 5 6 12
当你只需要几个组合/排列时，此功能非常好用。传统方法需要生成所有的组合/排列，然后再进行子集操作。在该示例中，这将导致无法完成，因为结果超过了10^17个（即ncombinations(1000, 7, bigz = TRUE) = 194280608456793000）。
结合arrangements生成器的改进，此功能使得内存使用效率非常高。
RcppAlgos
- 输出结果按字典序排序。
- 有方便的约束条件功能，我们不会在此讨论，因为它们与此问题无关。我只想指出，利用这些特性可以解决的问题类型是创建此包的动机（分区、子集和等）。
- GMP支持允许探索具有多个结果的向量的组合/排列。
- 使用
Parallel或nThreads参数并行生成结果。 - 类似于
combn，有一个FUN参数，用于对每个结果应用函数（也可以看看FUN.VALUE）。 - 提供灵活和内存高效的迭代器，允许双向迭代以及随机访问。
nextItem|nextNIter|nextRemaining：检索下一个字典序结果prevItem|prevNIter|prevRemaining：检索前一个字典序结果front|back|[[：随机访问方法- 允许轻松生成从任何起始位置开始的超过
2^31 - 1个结果。
观察：
iter <- RcppAlgos::comboIter(1000, 7)
# first combinations
iter@nextIter()
#> [1] 1 2 3 4 5 6 7
# next 5 combinations
iter@nextNIter(5)
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,] 1 2 3 4 5 6 8
#> [2,] 1 2 3 4 5 6 9
#> [3,] 1 2 3 4 5 6 10
#> [4,] 1 2 3 4 5 6 11
#> [5,] 1 2 3 4 5 6 12
# from the current state, the previous combination
iter@prevIter()
#> [1] 1 2 3 4 5 6 11
# the last combination
iter@back()
#> [1] 994 995 996 997 998 999 1000
# the 5th combination
iter[[5]]
#> [1] 1 2 3 4 5 6 11
# you can even pass a vector of indices
iter[[c(1, 3, 5)]]
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,] 1 2 3 4 5 6 7
#> [2,] 1 2 3 4 5 6 9
#> [3,] 1 2 3 4 5 6 11
# start iterating from any index
iter[[gmp::pow.bigz(2, 31)]]
#> [1] 1 2 3 17 138 928 954
# get useful info about the current state
iter@summary()
#> $description
#> [1] "Combinations of 1000 choose 7"
#>
#> $currentIndex
#> Big Integer ('bigz') :
#> [1] 2147483648
#>
#> $totalResults
#> Big Integer ('bigz') :
#> [1] 194280608456793000
#>
#> $totalRemaining
#> Big Integer ('bigz') :
#> [1] 194280606309309352
## get next ieteration
iter@nextIter()
#> [1] 1 2 3 17 138 928 955
如果你想了解每个软件包如何扩展，我会给你留下这个最后的例子，测量
RcppAlgos和arrangements软件包生成超过1亿个结果的速度。需要注意的是，这里排除了gtools::combinations，因为它会抛出错误：evaluation nested too deeply...。我们也排除combn，因为执行时间很长。有趣的是，在使用?utils::combn下“作者”一节中，utils::combn和combinat::combn之间的内存使用差异非常奇怪，因为它们只是稍微不同。
观察：
set.seed(2187)
tVec7 <- sort(sample(10^7, 10^3))
## 166,167,000 Combinations
system.time(RcppAlgos::comboGeneral(tVec7, 3))
#> user system elapsed
#> 0.386 0.105 0.490
system.time(arrangements::combinations(x = tVec7, k = 3))
#> user system elapsed
#> 0.439 0.105 0.545
## 124,251,000 Permuations
system.time(RcppAlgos::permuteGeneral(tVec7[1:500], 3))
#> user system elapsed
#> 0.141 0.076 0.218
system.time(arrangements::permutations(x = tVec7[1:500], k = 3))
#> user system elapsed
#> 0.386 0.077 0.463
7. 内存
在执行comboGeneral和arrangements::combinations时，在调用gc之前，内存将跳跃近2 Gb。这似乎是正确的，因为#rows * #nols * bytesPerCell / 2^30 bytes = choose(1000,3) * 3 * 4 / 2^30 bytes = (166167000 * 3 * 4)/2^30 = 1.857 Gbs）。然而，在执行combn时，内存行为是不稳定的（例如有时会使用全部16 Gb的内存，而其他时候只会暴增几个Gb）。当我在Windows环境下测试时，它经常会崩溃。
我们可以使用Rprof和summaryRporf来确认这一点。观察：
Rprof("RcppAlgos.out", memory.profiling = TRUE)
t1 <- RcppAlgos::comboGeneral(tVec7, 3)
Rprof(NULL)
head(summaryRprof("RcppAlgos.out", memory = "both")$by.total, n = 1)
#> total.time total.pct mem.total self.time self.pct
#> "RcppAlgos::comboGeneral" 0.42 100 1902 0.42 100
Rprof("arrangements.out", memory.profiling = TRUE)
t3 <- arrangements::combinations(tVec7, 3)
Rprof(NULL)
head(summaryRprof("arrangements.out", memory = "both")$by.total, n = 1)
#> total.time total.pct mem.total self.time self.pct
#> "arrangements::combinations" 0.5 100 1902 0.5 100
使用RcppAlgos和arrangements，mem.total仅占用略超过1900 Mb。
这是一个较小向量的内存配置文件。
tVec7Prime <- tVec7[1:300]
Rprof("combinat.out", memory.profiling = TRUE)
t3 <- combinat::combn(tVec7Prime, 3)
Rprof(NULL)
head(summaryRprof("combinat.out", memory = "both")$by.total, n = 1)
#> total.time total.pct mem.total self.time self.pct
#> "combinat::combn" 2.1 100 1055 1.98 94.29
Rprof("utils.out", memory.profiling = TRUE)
t4 <- utils::combn(tVec7Prime, 3)
Rprof(NULL)
head(summaryRprof("utils.out", memory = "both")$by.total, n = 1)
#> total.time total.pct mem.total self.time self.pct
#> "utils::combn" 1.6 100 2059 1.6 100
Rprof("gtools.out", memory.profiling = TRUE)
t5 <- gtools::combinations(300, 3, tVec7Prime)
Rprof(NULL)
head(summaryRprof("gtools.out", memory = "both")$by.total, n = 1)
#> total.time total.pct mem.total self.time self.pct
#> "rbind" 1.62 100 6659 1.46 90.12
有趣的是，utils::combn和combinat::combn使用不同的内存量并且执行所需的时间也不同。但是对于较小的向量，这种情况并不成立：
microbenchmark(combinat::combn(2:13, 6), utils::combn(2:13, 6))
#> Unit: microseconds
#> expr min lq mean median uq max neval
#> combinat::combn(2:13, 6) 313.4 326.7 329.4 328.1 330.4 370.6 100
#> utils::combn(2:13, 6) 378.3 393.1 397.0 395.2 399.2 451.2 100
使用
gtools 的总内存使用量比 utils 高出约3倍。需要注意的是，对于这三个软件包，每次运行时我都会得到不同的结果（例如，对于 combinat::combn ，有时我会得到9000 Mb，然后我会得到13000 Mb）。尽管如此，没有任何一个可以与
RcppAlgos 或 arrangements 相媲美。在上面的示例中，两者的内存使用量仅为51 Mb。基准测试脚本：https://github.com/jwood000/RcppAlgos/blob/main/scripts/SO_Comb_Perm_in_R.R *：向 Miklós Bóna 的《组合数学》致敬
- Joseph Wood
8
优秀的评论！我猜我明白了为什么在某些情况下，iterpc的性能不如RcppAlgos，因为生成器的本质不同。iterpc需要在执行实际算法之前初始化一个生成器对象。我正在将iterpc重构为一个新的包，并自相矛盾地试图摆脱RCpp，仅使用R C api。再次感谢优秀的包RcppAlgos！ - Randy Lai
@RandyLai，感谢你的赞美之词。我很高兴这篇评论能在某种程度上帮到你。我听说 R 中的 C API 至少可以说是“棘手”。祝你实现目标。 - Joseph Wood
@JosephWood 我在排列方面遇到了问题。我想知道
permuteGeneral()函数是否可以应用于列表中的列表，以计算所有可能的排列。例如，expand.grid(1:10,1:100,1:5)会给出不同长度的排列向量。它也适用于列表。考虑我有一个列表mylist = list(list(c(1,2,3,3,4),c(10,20,30,30,40,40,40,55)),list(c(2,4,6,6),1:10,1:50))，如果我使用sapply(mylist,expand.grid)，它会给出预期的结果。我想知道是否可以使用permuteGeneral()函数来完成这个操作，因为expand.grid()函数在高维度下需要很长时间。 - maydin2我感到非常惊讶！这是对该主题的彻底探索！谢谢！ - Reuben Mathew
1@jangorecki，我所知道的唯一基本R解决方案是包括在内的
combn。还有其他基本R解决方案吗？如果有，我很乐意添加。我能想到的另一个基本R解决方案是一些人可能认为应该包括的expand.grid。这个函数的问题在于它不提供排列或组合，而是笛卡尔积，这在本质上是不同的。 - Joseph Wood显示剩余3条评论
34
编辑: 我已更新答案，使用更高效的arrangements包。
使用arrangements入门
arrangements包含一些有效的生成器和迭代器用于排列组合。已经证明arrangements的性能超过了大部分类似的包。一些基准测试可以在这里找到。
这里是上述问题的答案。
# 1) combinations: without replacement: distinct items
combinations(5, 2)
[,1] [,2]
[1,] 1 2
[2,] 1 3
[3,] 1 4
[4,] 1 5
[5,] 2 3
[6,] 2 4
[7,] 2 5
[8,] 3 4
[9,] 3 5
[10,] 4 5
# 2) combinations: with replacement: distinct items
combinations(5, 2, replace=TRUE)
[,1] [,2]
[1,] 1 1
[2,] 1 2
[3,] 1 3
[4,] 1 4
[5,] 1 5
[6,] 2 2
[7,] 2 3
[8,] 2 4
[9,] 2 5
[10,] 3 3
[11,] 3 4
[12,] 3 5
[13,] 4 4
[14,] 4 5
[15,] 5 5
# 3) combinations: without replacement: non distinct items
combinations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2)
[,1] [,2]
[1,] "a" "a"
[2,] "a" "b"
[3,] "a" "c"
[4,] "b" "c"
# 4) combinations: with replacement: non distinct items
combinations(x = c("a", "b", "c"), k = 2, replace = TRUE) # as `freq` does not matter
[,1] [,2]
[1,] "a" "a"
[2,] "a" "b"
[3,] "a" "c"
[4,] "b" "b"
[5,] "b" "c"
[6,] "c" "c"
# 5) permutations: without replacement: distinct items
permutations(5, 2)
[,1] [,2]
[1,] 1 2
[2,] 1 3
[3,] 1 4
[4,] 1 5
[5,] 2 1
[6,] 2 3
[7,] 2 4
[8,] 2 5
[9,] 3 1
[10,] 3 2
[11,] 3 4
[12,] 3 5
[13,] 4 1
[14,] 4 2
[15,] 4 3
[16,] 4 5
[17,] 5 1
[18,] 5 2
[19,] 5 3
[20,] 5 4
# 6) permutations: with replacement: distinct items
permutations(5, 2, replace = TRUE)
[,1] [,2]
[1,] 1 1
[2,] 1 2
[3,] 1 3
[4,] 1 4
[5,] 1 5
[6,] 2 1
[7,] 2 2
[8,] 2 3
[9,] 2 4
[10,] 2 5
[11,] 3 1
[12,] 3 2
[13,] 3 3
[14,] 3 4
[15,] 3 5
[16,] 4 1
[17,] 4 2
[18,] 4 3
[19,] 4 4
[20,] 4 5
[21,] 5 1
[22,] 5 2
[23,] 5 3
[24,] 5 4
[25,] 5 5
# 7) permutations: without replacement: non distinct items
permutations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2)
[,1] [,2]
[1,] "a" "a"
[2,] "a" "b"
[3,] "a" "c"
[4,] "b" "a"
[5,] "b" "c"
[6,] "c" "a"
[7,] "c" "b"
# 8) permutations: with replacement: non distinct items
permutations(x = c("a", "b", "c"), k = 2, replace = TRUE) # as `freq` doesn't matter
[,1] [,2]
[1,] "a" "a"
[2,] "a" "b"
[3,] "a" "c"
[4,] "b" "a"
[5,] "b" "b"
[6,] "b" "c"
[7,] "c" "a"
[8,] "c" "b"
[9,] "c" "c"
与其他包的比较
使用 arrangements 相对于现有的包有几个优势。
积分框架：您不必为不同的方法使用不同的包。
它非常高效。请参见https://randy3k.github.io/arrangements/articles/benchmark.html以查看一些基准测试结果。
它具有内存效率，可以生成1到13的所有13！排列，因为矩阵大小的限制，现有的包将无法做到这一点。迭代器的
getnext()方法允许用户逐个获取排列。生成的排列按字典顺序排列，这可能是某些用户需要的。
- Randy Lai
6
3我认为通过展示一些输出结果来讲述每个“问题”的故事，可以改善这个答案。 - Jota
1这个回答是你的包装广告。如果你要这么做，请展示其各种功能以及为什么它们比先前的方法更优越。就我而言，这个问题和答案并没有取代所有关于组合/排列的其他问题（而且看起来这是你的意图）。 - Matthew Lundberg
1嗨，马修，很抱歉让你觉得这是一则广告（实际上确实是:)...）如果你去查看我的回答的编辑历史，你会发现旧的回答使用了其他的包。特别地，没有一个包可以对多集进行k排列，可以在这里看到自己编写的home-brew函数here。由于我对现有的包不满意，所以我决定编写自己的包。 - Randy Lai
但是我同意你的观点，我应该将我的软件包与现有的软件包进行比较。 - Randy Lai
我可以建议您更改函数名称。
gtools中的combinations/permutations函数被广泛使用，您的软件包可能会破坏依赖项/旧代码等。在开发软件包时，我喜欢使用@DirkEddelbuettel所表达的格言：“不要造成伤害”。 - Joseph Wood2我想一般来说这不是个问题，因为一个包调用另一个包中的函数的推荐方式是
<package>::<function>。除非涉及到脚本，拥有相似的名称不会造成太大的影响......在我看来。 - Randy Lai0
包crossdes似乎是值得加入列表的一个好选择。 请查看这个教程。
如果那个链接中的信息丢失了，我会从教程中复制文本。
对于BIBD，有v个处理重复r次，在k个观测块中重复b次。还有第五个参数lambda，记录每对处理在设计中出现的块数。
我们首先在会话中加载crossdes包：
require(crossdes)
函数find.BIB用于生成具有特定处理数、块数（设计的行数）和每个块中元素数（设计的列数）的区组设计。
考虑一个例子，其中有五个处理，分为四个块，每个块有三个元素。我们可以通过以下方式创建一个区组设计：
> find. BIB(5, 4, 3)
[,1] [,2] [,3]
[1,] 1 3 4
[2,] 2 4 5
[3,] 2 3 5
[4,] 1 2 5
这个设计不是BIBD，因为在设计中处理并没有重复相同的次数，我们可以使用isGYD函数来检查。例如：
> isGYD(find. BIB(5, 4, 3))
[1] The design is neither balanced w.r.t. rows nor w.r.t. columns.
这证实了我们从设计中所能看到的。
教程继续介绍了七个处理、七个块和三个元素，但我不会包括它们。
- DavidS
1
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接