r - R中重复数据集的排列

Question

我正在使用 R 生成一个向量的排列，其中包含重复项。

在生成排列时，我使用数字来表示组。这是我可以为 child 子做的事情:

unlist(unique(permn(c(1,1,2,2,3,3,4,4), paste0, collapse = "")))

它返回一个包含 2520 个排列的向量 (8!/2^4)

问题是我试图将其滚动到 11，以便我可以获得 16 选择 11 的每个唯一排列。为了获得我所做的每个组合:

combs = unique(combn(c(1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4),11, paste0, collapse = ""))

然后将遍历它们并将它们粘贴在一起以获得所有独特的 16 选择 11 排列。

听起来是个很大的数字？

不是。它是 525,525 行，理论上 (16!/5!4!4!4!4!) 问题是这种方法必须以 3900 万(11!)为一组计算所有 174356582400 行(大约是 1740 亿行)并执行对它们的独特操作。

是否有一种方法可以在查找排列时在复制中使用快捷方式和因子？

查看其他方法，我发现这会起作用:

unique(permutations(16,11, c(1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4), set=FALSE))

除了它花太多时间做这件事，而且它做的事情和我上面做的一样

Answer 1

你要找的是multisets的排列.

library(RcppAlgos)

multiPerm <- permuteGeneral(1:4, freqs = rep(2,4))

head(multiPerm)
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]    1    1    2    2    3    3    4    4
[2,]    1    1    2    2    3    4    3    4
[3,]    1    1    2    2    3    4    4    3
[4,]    1    1    2    2    4    3    3    4
[5,]    1    1    2    2    4    3    4    3
[6,]    1    1    2    2    4    4    3    3

完整性检查:

library(combinat)
library(gtools)
OPTestOne <- unlist(unique(permn(c(1,1,2,2,3,3,4,4), paste0, collapse = "")))
all.equal(sort(apply(multiPerm, 1, paste, collapse="")), sort(OPTestOne))
[1] TRUE

OPTestTwo <- unique(permutations(8,8,c(1,1,2,2,3,3,4,4), set=FALSE))
all.equal(OPTestTwo, multiPerm)
[1] TRUE  

以下是一些基准:

library(microbenchmark)
microbenchmark(OP_One = unique(permn(c(1,1,2,2,3,3,4,4), paste0, collapse = "")),
               Algos = permuteGeneral(1:4, freqs = rep(2,4)),
               OP_Two = unique(permutations(8,8,c(1,1,2,2,3,3,4,4), set=FALSE)),
               times = 5, unit = "relative")
Unit: relative
  expr      min        lq      mean   median       uq       max neval
OP_One  8435.40  5570.476  5877.457 5562.094 5378.490  5409.687     5
 Algos     1.00     1.000     1.000    1.000    1.000     1.000     5
OP_Two 15335.55 10095.646 10700.802 9982.139 9539.425 10295.974     5

寻找多重集的排列选择 m 也没有问题。

system.time(multiPermChoose11 <- permuteGeneral(1:4, m = 11, freqs = rep(4, 4)))
 user  system elapsed 
0.154   0.023   0.178

head(multiPermChoose11)
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
[1,]    1    1    1    1    2    2    2    2    3     3     3
[2,]    1    1    1    1    2    2    2    3    2     3     3
[3,]    1    1    1    1    2    2    2    3    3     2     3
[4,]    1    1    1    1    2    2    2    3    3     3     2
[5,]    1    1    1    1    2    2    3    2    2     3     3
[6,]    1    1    1    1    2    2    3    2    3     2     3

OP 对后一个示例有多少排列 (525,525) 的猜测是不正确的。发现这是一个 little more involved比提供的一个类轮。

nrow(multiPermChoose11)
[1] 2310000

只是为了表明这是正确的:

length(unique(apply(multiPermChoose11, 1, paste, collapse ="")))
[1] 2310000

还有一个来自 iterpc 的功能计算称为 np_multiset 的多重集的排列数

iterpc::np_multiset(rep(4,4), 11)
[1] 2310000

有关 R 中此类问题的更多信息，我写了一个 thorough overview问题: R: Permutations and combinations with/without replacement and for distinct/non-distinct items/multiset @RandyLai(作者 arrangements 和 iterpc ，两者都能够有效地完成上述工作。)