所有长度的无序组合
Unordered combinations of all lengths
我正在寻找一个函数，return 我是一个向量的所有无序组合。例如
x <- c('red','blue','black')
uncomb(x)
[1]'red'
[2]'blue'
[3]'black'
[4]'red','blue'
[5]'blue','black'
[6]'red','black'
[7]'red','blue','black'
我猜某些库中有一个函数可以执行此操作，但找不到。我正在尝试使用 gtool 的 permutations，但这不是我要找的功能。
您可以在 combn() 函数的 m 参数上应用长度为 x 的序列。
x <- c("red", "blue", "black")
do.call(c, lapply(seq_along(x), combn, x = x, simplify = FALSE))
# [[1]]
# [1] "red"
#
# [[2]]
# [1] "blue"
#
# [[3]]
# [1] "black"
#
# [[4]]
# [1] "red" "blue"
#
# [[5]]
# [1] "red" "black"
#
# [[6]]
# [1] "blue" "black"
#
# [[7]]
# [1] "red" "blue" "black"
如果您更喜欢矩阵结果，则可以将 stringi::stri_list2matrix() 应用于上面的列表。
stringi::stri_list2matrix(
do.call(c, lapply(seq_along(x), combn, x = x, simplify = FALSE)),
byrow = TRUE
)
# [,1] [,2] [,3]
# [1,] "red" NA NA
# [2,] "blue" NA NA
# [3,] "black" NA NA
# [4,] "red" "blue" NA
# [5,] "red" "black" NA
# [6,] "blue" "black" NA
# [7,] "red" "blue" "black"
我是 re-directed 从 过来的，因为这是受骗目标之一。这是一个老问题，@RichScriven 提供的答案非常好，但我想为社区提供更多选项，这些选项可以说更自然、更高效（最后两个）。
我们首先注意到输出与 Power Set. Calling powerSet from the rje package, we see that indeed our output matches every element from the power set except the first element which is equivalent to the Empty Set:
非常相似
x <- c("red", "blue", "black")
rje::powerSet(x)
[[1]]
character(0) ## empty set equivalent
[[2]]
[1] "red"
[[3]]
[1] "blue"
[[4]]
[1] "red" "blue"
[[5]]
[1] "black"
[[6]]
[1] "red" "black"
[[7]]
[1] "blue" "black"
[[8]]
[1] "red" "blue" "black"
如果您不需要第一个元素，您可以轻松地在函数调用的末尾添加一个 [-1]，如下所示：rje::powerSet(x)[-1].
接下来的两个解决方案来自较新的软件包 arrangements 和 RcppAlgos（我是作者），这将为用户带来巨大的效率提升。这两个包都能够生成 Multisets.
的组合
Why is this important?
可以证明从A的幂集到multisetc(rep(emptyElement, length(A)), A)的所有组合选择length(A)有一个one-to-one mapping，其中emptyElement 是空集的表示（如零或空白）。考虑到这一点，观察：
## There is also a function called combinations in the
## rje package, so we fully declare the function with
## scope operator
library(arrangements)
arrangements::combinations(x = c("",x), k = 3, freq = c(2, rep(1, 3)))
[,1] [,2] [,3]
[1,] "" "" "red"
[2,] "" "" "blue"
[3,] "" "" "black"
[4,] "" "red" "blue"
[5,] "" "red" "black"
[6,] "" "blue" "black"
[7,] "red" "blue" "black"
library(RcppAlgos)
comboGeneral(c("",x), 3, freqs = c(2, rep(1, 3)))
[,1] [,2] [,3]
[1,] "" "" "red"
[2,] "" "" "blue"
[3,] "" "" "black"
[4,] "" "red" "blue"
[5,] "" "red" "black"
[6,] "" "blue" "black"
[7,] "red" "blue" "black"
如果您不喜欢处理空白元素 and/or 矩阵，您也可以 return 使用 lapply.
的列表
lapply(seq_along(x), comboGeneral, v = x)
[[1]]
[,1]
[1,] "red"
[2,] "blue"
[3,] "black"
[[2]]
[,1] [,2]
[1,] "red" "blue"
[2,] "red" "black"
[3,] "blue" "black"
[[3]]
[,1] [,2] [,3]
[1,] "red" "blue" "black"
lapply(seq_along(x), function(y) arrangements::combinations(x, y))
[[1]]
[,1]
[1,] "red"
[2,] "blue"
[3,] "black"
[[2]]
[,1] [,2]
[1,] "red" "blue"
[2,] "red" "black"
[3,] "blue" "black"
[[3]]
[,1] [,2] [,3]
[1,] "red" "blue" "black"
现在我们证明最后两种方法更有效（N.B。我从@RichSciven 提供的答案中删除了 do.call(c, 和 simplify = FALSE，以便比较生成类似的输出。我还包括 rje::powerSet 以备不时之需):
set.seed(8128)
bigX <- sort(sample(10^6, 20)) ## With this as an input, we will get 2^20 - 1 results.. i.e. 1,048,575
library(microbenchmark)
microbenchmark(powSetRje = powerSet(bigX),
powSetRich = lapply(seq_along(bigX), combn, x = bigX),
powSetArrange = lapply(seq_along(bigX), function(y) arrangements::combinations(x = bigX, k = y)),
powSetAlgos = lapply(seq_along(bigX), comboGeneral, v = bigX),
unit = "relative")
Unit: relative
expr min lq mean median uq max neval
powSetRje 64.4252454 44.063199 16.678438 18.63110 12.082214 7.317559 100
powSetRich 61.6766640 43.027789 16.009151 17.88944 11.406994 7.222899 100
powSetArrange 0.9508052 1.060309 1.080341 1.02257 1.262713 1.126384 100
powSetAlgos 1.0000000 1.000000 1.000000 1.00000 1.000000 1.000000 100
更进一步，arrangements 配备了一个名为 layout 的参数，它允许用户为其输出选择特定格式。其中之一是列表的 layout = "l"。它类似于在 combn 中设置 simplify = FALSE 并允许我们获得类似于 powerSet 的输出。观察：
do.call(c, lapply(seq_along(x), function(y) {
arrangements::combinations(x, y, layout = "l")
}))
[[1]]
[1] "red"
[[2]]
[1] "blue"
[[3]]
[1] "black"
[[4]]
[1] "red" "blue"
[[5]]
[1] "red" "black"
[[6]]
[1] "blue" "black"
[[7]]
[1] "red" "blue" "black"
和基准：
microbenchmark(powSetRje = powerSet(bigX)[-1],
powSetRich = do.call(c, lapply(seq_along(bigX), combn, x = bigX, simplify = FALSE)),
powSetArrange = do.call(c, lapply(seq_along(bigX), function(y) arrangements::combinations(bigX, y, layout = "l"))),
times = 15, unit = "relative")
Unit: relative
expr min lq mean median uq max neval
powSetRje 5.539967 4.785415 4.277319 4.387410 3.739593 3.543570 15
powSetRich 4.994366 4.306784 3.863612 3.932252 3.334708 3.327467 15
powSetArrange 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 15 15
不使用任何外部包的矩阵结果解决方案：
store <- lapply(
seq_along(x),
function(i) {
out <- combn(x, i)
N <- NCOL(out)
length(out) <- length(x) * N
matrix(out, ncol = N, byrow = TRUE)
})
t(do.call(cbind, store))
[,1] [,2] [,3]
[1,] "red" NA NA
[2,] "blue" NA NA
[3,] "black" NA NA
[4,] "red" "black" NA
[5,] "blue" "blue" NA
[6,] "red" "black" NA
[7,] "red" "blue" "black"
我正在寻找一个函数，return 我是一个向量的所有无序组合。例如
x <- c('red','blue','black')
uncomb(x)
[1]'red'
[2]'blue'
[3]'black'
[4]'red','blue'
[5]'blue','black'
[6]'red','black'
[7]'red','blue','black'
我猜某些库中有一个函数可以执行此操作，但找不到。我正在尝试使用 gtool 的 permutations，但这不是我要找的功能。
您可以在 combn() 函数的 m 参数上应用长度为 x 的序列。
x <- c("red", "blue", "black")
do.call(c, lapply(seq_along(x), combn, x = x, simplify = FALSE))
# [[1]]
# [1] "red"
#
# [[2]]
# [1] "blue"
#
# [[3]]
# [1] "black"
#
# [[4]]
# [1] "red" "blue"
#
# [[5]]
# [1] "red" "black"
#
# [[6]]
# [1] "blue" "black"
#
# [[7]]
# [1] "red" "blue" "black"
如果您更喜欢矩阵结果，则可以将 stringi::stri_list2matrix() 应用于上面的列表。
stringi::stri_list2matrix(
do.call(c, lapply(seq_along(x), combn, x = x, simplify = FALSE)),
byrow = TRUE
)
# [,1] [,2] [,3]
# [1,] "red" NA NA
# [2,] "blue" NA NA
# [3,] "black" NA NA
# [4,] "red" "blue" NA
# [5,] "red" "black" NA
# [6,] "blue" "black" NA
# [7,] "red" "blue" "black"
我是 re-directed 从
我们首先注意到输出与 Power Set. Calling powerSet from the rje package, we see that indeed our output matches every element from the power set except the first element which is equivalent to the Empty Set:
x <- c("red", "blue", "black")
rje::powerSet(x)
[[1]]
character(0) ## empty set equivalent
[[2]]
[1] "red"
[[3]]
[1] "blue"
[[4]]
[1] "red" "blue"
[[5]]
[1] "black"
[[6]]
[1] "red" "black"
[[7]]
[1] "blue" "black"
[[8]]
[1] "red" "blue" "black"
如果您不需要第一个元素，您可以轻松地在函数调用的末尾添加一个 [-1]，如下所示：rje::powerSet(x)[-1].
接下来的两个解决方案来自较新的软件包 arrangements 和 RcppAlgos（我是作者），这将为用户带来巨大的效率提升。这两个包都能够生成 Multisets.
Why is this important?
可以证明从A的幂集到multisetc(rep(emptyElement, length(A)), A)的所有组合选择length(A)有一个one-to-one mapping，其中emptyElement 是空集的表示（如零或空白）。考虑到这一点，观察：
## There is also a function called combinations in the
## rje package, so we fully declare the function with
## scope operator
library(arrangements)
arrangements::combinations(x = c("",x), k = 3, freq = c(2, rep(1, 3)))
[,1] [,2] [,3]
[1,] "" "" "red"
[2,] "" "" "blue"
[3,] "" "" "black"
[4,] "" "red" "blue"
[5,] "" "red" "black"
[6,] "" "blue" "black"
[7,] "red" "blue" "black"
library(RcppAlgos)
comboGeneral(c("",x), 3, freqs = c(2, rep(1, 3)))
[,1] [,2] [,3]
[1,] "" "" "red"
[2,] "" "" "blue"
[3,] "" "" "black"
[4,] "" "red" "blue"
[5,] "" "red" "black"
[6,] "" "blue" "black"
[7,] "red" "blue" "black"
如果您不喜欢处理空白元素 and/or 矩阵，您也可以 return 使用 lapply.
lapply(seq_along(x), comboGeneral, v = x)
[[1]]
[,1]
[1,] "red"
[2,] "blue"
[3,] "black"
[[2]]
[,1] [,2]
[1,] "red" "blue"
[2,] "red" "black"
[3,] "blue" "black"
[[3]]
[,1] [,2] [,3]
[1,] "red" "blue" "black"
lapply(seq_along(x), function(y) arrangements::combinations(x, y))
[[1]]
[,1]
[1,] "red"
[2,] "blue"
[3,] "black"
[[2]]
[,1] [,2]
[1,] "red" "blue"
[2,] "red" "black"
[3,] "blue" "black"
[[3]]
[,1] [,2] [,3]
[1,] "red" "blue" "black"
现在我们证明最后两种方法更有效（N.B。我从@RichSciven 提供的答案中删除了 do.call(c, 和 simplify = FALSE，以便比较生成类似的输出。我还包括 rje::powerSet 以备不时之需):
set.seed(8128)
bigX <- sort(sample(10^6, 20)) ## With this as an input, we will get 2^20 - 1 results.. i.e. 1,048,575
library(microbenchmark)
microbenchmark(powSetRje = powerSet(bigX),
powSetRich = lapply(seq_along(bigX), combn, x = bigX),
powSetArrange = lapply(seq_along(bigX), function(y) arrangements::combinations(x = bigX, k = y)),
powSetAlgos = lapply(seq_along(bigX), comboGeneral, v = bigX),
unit = "relative")
Unit: relative
expr min lq mean median uq max neval
powSetRje 64.4252454 44.063199 16.678438 18.63110 12.082214 7.317559 100
powSetRich 61.6766640 43.027789 16.009151 17.88944 11.406994 7.222899 100
powSetArrange 0.9508052 1.060309 1.080341 1.02257 1.262713 1.126384 100
powSetAlgos 1.0000000 1.000000 1.000000 1.00000 1.000000 1.000000 100
更进一步，arrangements 配备了一个名为 layout 的参数，它允许用户为其输出选择特定格式。其中之一是列表的 layout = "l"。它类似于在 combn 中设置 simplify = FALSE 并允许我们获得类似于 powerSet 的输出。观察：
do.call(c, lapply(seq_along(x), function(y) {
arrangements::combinations(x, y, layout = "l")
}))
[[1]]
[1] "red"
[[2]]
[1] "blue"
[[3]]
[1] "black"
[[4]]
[1] "red" "blue"
[[5]]
[1] "red" "black"
[[6]]
[1] "blue" "black"
[[7]]
[1] "red" "blue" "black"
和基准：
microbenchmark(powSetRje = powerSet(bigX)[-1],
powSetRich = do.call(c, lapply(seq_along(bigX), combn, x = bigX, simplify = FALSE)),
powSetArrange = do.call(c, lapply(seq_along(bigX), function(y) arrangements::combinations(bigX, y, layout = "l"))),
times = 15, unit = "relative")
Unit: relative
expr min lq mean median uq max neval
powSetRje 5.539967 4.785415 4.277319 4.387410 3.739593 3.543570 15
powSetRich 4.994366 4.306784 3.863612 3.932252 3.334708 3.327467 15
powSetArrange 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 15 15
不使用任何外部包的矩阵结果解决方案：
store <- lapply(
seq_along(x),
function(i) {
out <- combn(x, i)
N <- NCOL(out)
length(out) <- length(x) * N
matrix(out, ncol = N, byrow = TRUE)
})
t(do.call(cbind, store))
[,1] [,2] [,3]
[1,] "red" NA NA
[2,] "blue" NA NA
[3,] "black" NA NA
[4,] "red" "black" NA
[5,] "blue" "blue" NA
[6,] "red" "black" NA
[7,] "red" "blue" "black"