R 中重复数据集的排列

Question

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

在生成排列时，我使用数字来表示组。以下是我能为小孩子做的事情：

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

您正在寻找的是多重集的排列。

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

v <- rep(1:4, each = 2)
v
#> [1] 1 1 2 2 3 3 4 4

## Also, utilize S3 'table' method
head(permuteGeneral(table(v)))
#>      [,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

或者使用包

arrangements

:

multiPerm2 <- arrangements::permutations(1:4, freq = rep(2, 4))

健全性检查：

identical(multiPerm, multiPerm2)
#> [1] TRUE

suppressWarnings(suppressMessages(library(combinat)))
library(gtools)

OPTestOne <- unlist(unique(permn(v, paste0, collapse = "")))
all.equal(sort(apply(multiPerm, 1, paste, collapse = "")),
          sort(OPTestOne))
#> [1] TRUE

OPTestTwo <- unique(permutations(8, 8, v, set = FALSE))
all.equal(OPTestTwo, multiPerm)
#> [1] TRUE

以下是一些基准：

library(microbenchmark)
options(digits = 4)

microbenchmark(OP_One = unique(permn(v, paste0, collapse = "")),
               Arnge = arrangements::permutations(1:4, freq = rep(2, 4)),
               OP_Two = unique(permutations(8, 8, v, set = FALSE)),
               times = 5, unit = "relative")
#> Warning in microbenchmark(OP_One = unique(permn(v, paste0, collapse = "")), :
#> less accurate nanosecond times to avoid potential integer overflows
#> Unit: relative
#>    expr       min       lq     mean   median       uq      max neval
#>  OP_One  5535.712 3981.265 4227.581 3757.520 4038.301 4282.094     5
#>   Arnge     1.000    1.000    1.000    1.000    1.000    1.000     5
#>  OP_Two 10327.193 7449.043 7719.485 7207.863 7435.751 7155.603     5

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

system.time(
    permuteGeneral(1:4, m = 11, freqs = rep(4, 4))
)
#>    user  system elapsed 
#>   0.021   0.003   0.024

system.time(
    arrangements::permutations(1:4, 11, freq = rep(4, 4))
)
#>    user  system elapsed 
#>   0.024   0.006   0.028

OP 对后一个例子的排列数量 (525,525) 的猜测是不正确的。找到这个比提供的一个班轮更复杂一点。

permuteCount(table(rep(1:4, each = 4)), m = 11)
#> [1] 2310000

arrangements::npermutations(1:4, 11, freq = rep(4, 4))
#> [1] 2310000

只是为了表明这些都是独一无二的：

length(
    unique(
        apply(
            permuteGeneral(1:4, m = 11, freqs = rep(4, 4)),
            MARGIN = 1, paste, collapse = ""
        )
    )
)
#> [1] 2310000

有关 R 中此类问题的更多信息，我针对该问题编写了

全面概述

：如何在 R 中生成对象的排列或组合？ 作者：@RandyLai（arrangements的作者）