R:分区排列的高效计算

Question

给定一个包含 n 个唯一元素的向量:

x <- c('a','b','c')

我想为任意 n 找到 x 所有分区的所有排列。对于 n=3，这意味着 13 个排序:

('a', 'b', 'c')
('a') ('b','c')
('b','c') ('a')
('a','b') ('c')
('a','c') ('b')
('b') ('a','c')
('c') ('b','a')
('a') ('b') ('c')
('a') ('c') ('b')
('b') ('a') ('c')
('b') ('c') ('a')
('c') ('a') ('b')
('c') ('b') ('a')

可以使用 partitions 库中的 listParts 找到分区(不幸的是，setparts 似乎与最新版本的 R 不兼容) ，以及 combinat 包中的 permn 的排列:

library(partitions)
library(combinat)
parts <- listParts(length(x))

p1 <- permn(parts[[1]])
p2 <- permn(parts[[2]])
...

但是，我很难找到一种有效的方法来排列分区和存储结果。我的目标是将结果映射到类似

的结构

  a b c
1 1 1 1
2 1 2 2
3 2 1 1
4 1 1 2 
...

其中整数表示排列中元素的顺序。由于分区在内部是无序的，因此分区中的任何元素都将获得相同的整数等级。似乎应该有某种方法可以通过引用分区的列表索引来有效地执行此操作，但我无法找到一种方法来执行此操作。

Answer 1

这里是一个简短的片段，可以得到预期的结果:

x <- c('a','b','c')

## Probably not a good idea to name this parts as there
## is a function in the partitions package called parts
myParts <- partitions::listParts(length(x))

permParts <- unlist(lapply(seq_along(x), function(j) {
    tempParts <- myParts[lengths(myParts) == j]
    perms <- combinat::permn(j)

    unlist(lapply(tempParts, function(p) {
        lapply(perms, function(q) {
            t <- lapply(p[q], function(i) x[i])
            class(t) <- c("list", "equivalence")
            t
        })
    }), recursive = F)
}), recursive = F)

这是给定示例的输出:

permParts
[[1]]
[1] (a,b,c)

[[2]]
[1] (a,c)(b)

[[3]]
[1] (b)(a,c)

[[4]]
[1] (a,b)(c)

[[5]]
[1] (c)(a,b)

[[6]]
[1] (b,c)(a)

[[7]]
[1] (a)(b,c)

[[8]]
[1] (a)(b)(c)

[[9]]
[1] (a)(c)(b)

[[10]]
[1] (c)(a)(b)

[[11]]
[1] (c)(b)(a)

[[12]]
[1] (b)(c)(a)

[[13]]
[1] (b)(a)(c)

我不会说以上必然是最有效的解决方案，但如果不滚动您的算法，我想不出更有效的攻击。<​​/p>