在R中生成列表的所有不同排列

Question

我正在尝试创建一个列表的排列组合，例如perms(list("a", "b", "c"))返回：

list(list("a", "b", "c"), list("a", "c", "b"), list("b", "a", "c"),
     list("b", "c", "a"), list("c", "a", "b"), list("c", "b", "a"))

我不确定该如何继续，非常感谢任何帮助。

- tresbot

---

在R语言中有几个用于生成排列的包。我写了一个**摘要**，其中包括每种可用方法的演示以及基准测试结果。 - Joseph Wood

Answer 1

有一段时间之前，我需要在不加载任何包的情况下使用基础R来完成这个任务。

permutations <- function(n){
    if(n==1){
        return(matrix(1))
    } else {
        sp <- permutations(n-1)
        p <- nrow(sp)
        A <- matrix(nrow=n*p,ncol=n)
        for(i in 1:n){
            A[(i-1)*p+1:p,] <- cbind(i,sp+(sp>=i))
        }
        return(A)
    }
}

使用方法：

> matrix(letters[permutations(3)],ncol=3)
     [,1] [,2] [,3]
[1,] "a"  "b"  "c" 
[2,] "a"  "c"  "b" 
[3,] "b"  "a"  "c" 
[4,] "b"  "c"  "a" 
[5,] "c"  "a"  "b" 
[6,] "c"  "b"  "a" 

- Museful

---

不错的函数。看起来速度也很快。 - A5C1D2H2I1M1N2O1R2T1

这个函数比combinat::permn在更大数量的排列中要快得多。例如： microbenchmark:microbenchmark(permn(letters[1:9]), matrix(letters[permutations(9)],ncol=9), times=20) - Anthony

Answer 2

combinat::permn可以完成这项工作：

> library(combinat)
> permn(letters[1:3])
[[1]]
[1] "a" "b" "c"

[[2]]
[1] "a" "c" "b"

[[3]]
[1] "c" "a" "b"

[[4]]
[1] "c" "b" "a"

[[5]]
[1] "b" "c" "a"

[[6]]
[1] "b" "a" "c"

请注意，如果元素很大，计算量会非常大。

- kohske

---

如果我们不仅想要所有三个字母元素，还想要两个字母和一个字母的元素，该怎么办？ - Przemyslaw Remin

函数能接受的向量元素的最大数量是多少？ - Tonny Anthony

Answer 3

基础的 R 也可以提供答案：

all <- expand.grid(p1 = letters[1:3], p2 = letters[1:3], p3 = letters[1:3], stringsAsFactors = FALSE) 
perms <- all[apply(all, 1, function(x) {length(unique(x)) == 3}),]

- Andrew

Answer 4

你可以尝试使用 gtools 包中的 permutations() 函数，但与 combinat 中的 permn() 不同，它不会输出列表。

> library(gtools)
> permutations(3, 3, letters[1:3])
     [,1] [,2] [,3]
[1,] "a"  "b"  "c" 
[2,] "a"  "c"  "b" 
[3,] "b"  "a"  "c" 
[4,] "b"  "c"  "a" 
[5,] "c"  "a"  "b" 
[6,] "c"  "b"  "a" 

- A5C1D2H2I1M1N2O1R2T1

---

值得注意的是，“permutations”更加灵活。它允许对n个元素中的m个元素进行排列，并允许重复使用元素。在尝试使用“permn”失败后，我发现了这一点。 - mt1022

当v源向量具有重复元素时，它无法生成所有可能的排列。因此，假设我想获取单词“letters”的所有可能排列。 - George Pipis

Answer 5

使用 R 基础功能的解决方案，不需要依赖其他包:

> getPermutations <- function(x) {
    if (length(x) == 1) {
        return(x)
    }
    else {
        res <- matrix(nrow = 0, ncol = length(x))
        for (i in seq_along(x)) {
            res <- rbind(res, cbind(x[i], Recall(x[-i])))
        }
        return(res)
    }
}

> getPermutations(letters[1:3])
     [,1] [,2] [,3]
[1,] "a"  "b"  "c" 
[2,] "a"  "c"  "b" 
[3,] "b"  "a"  "c" 
[4,] "b"  "c"  "a" 
[5,] "c"  "a"  "b" 
[6,] "c"  "b"  "a"

我希望这可以帮到你。

- Adrian

---

比 gtools 解决方案表现更好。 - s_baldur

之前没有测试过，但看起来是这样。很酷。 - Adrian

Answer 6

尝试：

> a = letters[1:3]
> eg = expand.grid(a,a,a)
> eg[!(eg$Var1==eg$Var2 | eg$Var2==eg$Var3 | eg$Var1==eg$Var3),]
   Var1 Var2 Var3
6     c    b    a
8     b    c    a
12    c    a    b
16    a    c    b
20    b    a    c
22    a    b    c

根据评论中 @Adrian 的建议，最后一行可以替换为：

eg[apply(eg, 1, anyDuplicated) == 0, ]

- rnso

---

或者，对于最后一行：“eg [apply（eg，1，anyDuplicated）== 0，]” - Adrian

关于可扩展性的说明：在“严肃”的代码中使用此方法之前，我会三思而后行，因为随着样本大小/采样集增加，搜索空间（例如）变得不合理地巨大（命中率：n！与n^n相比，近似于斯特林公式估算的指数级恶化）。对于10中的10个案例，命中率仅为 prod(1:10) / (10 ^ 10) = 0.036%。这些被检查过的变量似乎都存储在一个数据框中，并且我总是喜欢这种方法用于小型手动任务，因为它非常易于理解。 - brezniczky

@brezniczky 是的，确实如此，这只是为了演示目的。我有一个完全不同的解决方案（在这个线程下面），它是自包含的。两者都使用纯R语言，但当然对于更密集的内存操作，应该实现一些编译代码（实际上，大多数R的内部函数都是用C语言编写的）。 - Adrian

Answer 7

# Another recursive implementation    
# for those who like to roll their own, no package required 
    permutations <- function( x, prefix = c() )
    {
        if(length(x) == 0 ) return(prefix)
        do.call(rbind, sapply(1:length(x), FUN = function(idx) permutations( x[-idx], c( prefix, x[idx])), simplify = FALSE))
    }

    permutations(letters[1:3])
    #    [,1] [,2] [,3]
    #[1,] "a"  "b"  "c" 
    #[2,] "a"  "c"  "b" 
    #[3,] "b"  "a"  "c" 
    #[4,] "b"  "c"  "a" 
    #[5,] "c"  "a"  "b" 
    #[6,] "c"  "b"  "a" 

- Rick

---

很棒的答案！那么放弃sapply(..., simplify = FALSE)，改用lapply(...)怎么样？ - Benjamin Christoffersen

Answer 8

一个有趣的基于R语言的“概率”解决方案，使用样本：

elements <- c("a", "b", "c")
k <- length(elements)
res=unique(t(sapply(1:200, function(x) sample(elements, k))))
# below, check you have all the permutations you need (if not, try again)
nrow(res) == factorial(k)
res

基本上，您会调用许多随机样本，希望获得它们所有，并使它们唯一。

- Arnaud A

Answer 9

看这里，purrr解决方案：

> map(1:3, ~ c('a', 'b', 'c')) %>%
    cross() %>%
    keep(~ length(unique(.x)) == 3) %>%
    map(unlist)
#> [[1]]
#> [1] "c" "b" "a"
#> 
#> [[2]]
#> [1] "b" "c" "a"
#> 
#> [[3]]
#> [1] "c" "a" "b"
#> 
#> [[4]]
#> [1] "a" "c" "b"
#> 
#> [[5]]
#> [1] "b" "a" "c"
#> 
#> [[6]]
#> [1] "a" "b" "c"

- Dmitry Zotikov

Answer 10

我们可以使用基础函数combn并进行一些修改：

   combn_n <- function(x) {
      m <- length(x) - 1 # number of elements to choose: n-1 
      xr <- rev(x) # reversed x
      part_1 <- rbind(combn(x, m), xr, deparse.level = 0) 
      part_2 <- rbind(combn(xr, m), x, deparse.level = 0) 
      cbind(part_1, part_2)
       }

  combn_n(letters[1:3])

[,1] [,2] [,3] [,4] [,5] [,6]  
[1,] "a"  "a"  "b"  "c"  "c"  "b"   
[2,] "b"  "c"  "c"  "b"  "a"  "a"   
[3,] "c"  "b"  "a"  "a"  "b"  "c"   

- Eyayaw