简述
使用来自RcppAlgos
的comboGrid
:
library(RcppAlgos)
comboGrid(c("aa", "ab", "cc"), c("aa", "ab", "cc"))
Var1 Var2
[1,] "aa" "aa"
[2,] "aa" "ab"
[3,] "aa" "cc"
[4,] "ab" "ab"
[5,] "ab" "cc"
[6,] "cc" "cc"
细节
我最近遇到了这个问题R - Expand Grid Without Duplicates,在寻找重复项时,我发现了这个问题。那里的问题并不完全是一个重复项,因为它更加通用,并且有额外的限制,@Ferdinand.kraft也对此进行了一些阐述。
需要注意的是,这里的许多解决方案都使用了某种组合函数。 expand.grid
函数返回基本不同的笛卡尔积。
笛卡尔积作用于多个对象,这些对象可能相同,也可能不相同。一般来说,组合函数应用于单个向量。排列函数也可以这样说。
如果提供的向量不相同,则仅使用组合/排列函数将产生可比较的结果expand.grid
。作为一个非常简单的例子,考虑v1 = 1:3, v2 = 2:4
。
使用expand.grid
,我们可以看到第3行和第5行是重复的:
expand.grid(1:3, 2:4)
Var1 Var2
1 1 2
2 2 2
3 3 2
4 1 3
5 2 3
6 3 3
7 1 4
8 2 4
9 3 4
使用combn
并不能完全解决问题:
t(combn(unique(c(1:3, 2:4)), 2))
[,1] [,2]
[1,] 1 2
[2,] 1 3
[3,] 1 4
[4,] 2 3
[5,] 2 4
[6,] 3 4
使用gtools
进行重复操作,我们生成了太多的结果:
gtools::combinations(4, 2, v = unique(c(1:3, 2:4)), repeats.allowed = TRUE)
[,1] [,2]
[1,] 1 1
[2,] 1 2
[3,] 1 3
[4,] 1 4
[5,] 2 2
[6,] 2 3
[7,] 2 4
[8,] 3 3
[9,] 3 4
[10,] 4 4
事实上,我们生成的结果甚至不在笛卡尔积中(即
expand.grid
解决方案)。
我们需要一个可以创建以下内容的解决方案:
Var1 Var2
[1,] 1 2
[2,] 1 3
[3,] 1 4
[4,] 2 2
[5,] 2 3
[6,] 2 4
[7,] 3 3
[8,] 3 4
我编写了包
RcppAlgos
,在最新版本
v2.4.3
中,有一个名为
comboGrid
的函数可以解决这个问题。它非常通用、灵活且速度很快。
首先,回答提问者提出的具体问题:
library(RcppAlgos)
comboGrid(c("aa", "ab", "cc"), c("aa", "ab", "cc"))
Var1 Var2
[1,] "aa" "aa"
[2,] "aa" "ab"
[3,] "aa" "cc"
[4,] "ab" "ab"
[5,] "ab" "cc"
[6,] "cc" "cc"
正如@Ferdinand.kraft指出的那样,有时输出可能需要在给定行中排除重复项。为此,我们使用repetition = FALSE
:
comboGrid(c("aa", "ab", "cc"), c("aa", "ab", "cc"), repetition = FALSE)
Var1 Var2
[1,] "aa" "ab"
[2,] "aa" "cc"
[3,] "ab" "cc"
comboGrid
也非常通用,可以应用于多个向量:
comboGrid(rep(list(c("aa", "ab", "cc")), 3))
Var1 Var2 Var3
[1,] "aa" "aa" "aa"
[2,] "aa" "aa" "ab"
[3,] "aa" "aa" "cc"
[4,] "aa" "ab" "ab"
[5,] "aa" "ab" "cc"
[6,] "aa" "cc" "cc"
[7,] "ab" "ab" "ab"
[8,] "ab" "ab" "cc"
[9,] "ab" "cc" "cc"
[10,] "cc" "cc" "cc"
不需要向量完全相同:
comboGrid(1:3, 2:4)
Var1 Var2
[1,] 1 2
[2,] 1 3
[3,] 1 4
[4,] 2 2
[5,] 2 3
[6,] 2 4
[7,] 3 3
[8,] 3 4
并且可以应用于各种类型的向量:
set.seed(123)
my_range <- 3:15
mixed_types <- list(
int1 = sample(15, sample(my_range, 1)),
int2 = sample(15, sample(my_range, 1)),
char1 = sample(LETTERS, sample(my_range, 1)),
char2 = sample(LETTERS, sample(my_range, 1))
)
dim(expand.grid(mixed_types))
[1] 1950 4
dim(comboGrid(mixed_types, repetition = FALSE))
[1] 1595 4
dim(comboGrid(mixed_types, repetition = TRUE))
[1] 1770 4
该算法避免生成笛卡尔积并随后去重。最终,我们使用
算术基本定理创建哈希表,并采用
user2357112 supports Monica在
从具有重叠的池中选择无序组合的答案中指出的去重方法。所有这些加上它是用
C ++
编写的事实意味着它快速且内存效率高。
pools = list(c(1, 10, 14, 6),
c(7, 2, 4, 8, 3, 11, 12),
c(11, 3, 13, 4, 15, 8, 6, 5),
c(10, 1, 3, 2, 9, 5, 7),
c(1, 5, 10, 3, 8, 14),
c(15, 3, 7, 10, 4, 5, 8, 6),
c(14, 9, 11, 15),
c(7, 6, 13, 14, 10, 11, 9, 4),
c(6, 3, 2, 14, 7, 12, 9),
c(6, 11, 2, 5, 15, 7))
system.time(combCarts <- comboGrid(pools))
user system elapsed
0.929 0.062 0.992
nrow(combCarts)
[1] 1205740
print(object.size(combCarts), unit = "Mb")
92 Mb
system.time(cartProd <- expand.grid(pools))
user system elapsed
8.477 2.895 11.461
prod(lengths(pools))
[1] 101154816
print(object.size(cartProd), unit = "Mb")
7717.5 Mb