R：列出所有无方向的循环permutations/arrangements（即clockwise/anti-clockwise相同）

Question

如何列出 R 中方向无关紧要的所有循环排列？我有一个矢量 1:4 用于说明（但是，我想要一个通用的解决方案）。我用

gtools::permutations(n = 4, r = 4)

它列出了所有可能的排列，如下所示：

     [,1] [,2] [,3] [,4]
 [1,]    1    2    3    4
 [2,]    1    2    4    3
 [3,]    1    3    2    4
 [4,]    1    3    4    2
 [5,]    1    4    2    3
 [6,]    1    4    3    2
 [7,]    2    1    3    4
 [8,]    2    1    4    3
 [9,]    2    3    1    4
[10,]    2    3    4    1
[11,]    2    4    1    3
[12,]    2    4    3    1
[13,]    3    1    2    4
[14,]    3    1    4    2
[15,]    3    2    1    4
[16,]    3    2    4    1
[17,]    3    4    1    2
[18,]    3    4    2    1
[19,]    4    1    2    3
[20,]    4    1    3    2
[21,]    4    2    1    3
[22,]    4    2    3    1
[23,]    4    3    1    2
[24,]    4    3    2    1

不过，我想要的是六种循环排列的列表。所以，我认为这是：

cbind(gtools::permutations(n = 3, r = 3),4)

这给了我：

    [,1] [,2] [,3] [,4]
[1,]    1    2    3    4
[2,]    1    3    2    4
[3,]    2    1    3    4
[4,]    2    3    1    4
[5,]    3    1    2    4
[6,]    3    2    1    4

但是，我也想忽略相同但为了排序的列表。示例：我不想区分 c(1,2,3,4) 和 c(4,3,2,1)（即第 1 和第 6 个条目），或 c(1, 3, 2, 4) 和 c(2, 1, 3, 4)（即第 2 和第 4 个条目）和 c(3, 1, 2, 4) 中的 c(2, 1, 3, 4)（即输出中的第 3 和第 5 个条目）？仅仅是取前半部分结果的情况吗？

有没有更可靠的方法呢？非常感谢您回答我的问题或提供建议。

Answer 1

我们不能简单地取 permutations(n-1, n-1) 的前半部分结果并附加 n。这对于 n = 5 很容易看出。

我建议使用以下方法：

我们将第一个元素设置为始终为 1。这样我们就可以确保对于每组等价排列只进行 1 次排列。这与您将 4 始终作为示例中的最后一个元素所做的基本相同。
仅考虑元素 #2 小于元素 #n 的排列。对于第一个规则描述的集合中的每个排列，将有一个且只有一个与它相反的排列。通过这种方式，我们确保只对每一对进行一个排列。

这就是我们要用来构造这样一组排列的算法：

找到所有元素对 #2 和 #n，其中 #2 小于 #n。这是combinations(n-1, 2, v = 2:n).
对于每个这样的组合，找到所有其余 n-3 个元素的所有排列。这是 permutations(n - 3, n - 3, v = rest_elements)，其中 rest_elements 是一个向量，列出了当我们删除 1、#2 和 #n 时剩下的所有 n-3 个元素。

library(gtools)
get_perms <- function(n) {
  # 1 is always first, #2 and #n have to be such that #2 < #n
  # all combinations of elements #2 and #n:
  combs_2n <- combinations(n-1, 2, v = 2:n)
  # for each such combination we have n-3 elements left to place
  # it's (n-3)! variants
  n_perms_rest <- factorial(n - 3)
  # resulting matrix with placeholders for these element combinations
  res <- 
    cbind(
      1, # element 1
      rep(combs_2n[,1], each = n_perms_rest), #element 2
      matrix(nrow = n_perms_rest*nrow(combs_2n), ncol = n-3), # elements 2-(n-1)
      rep(combs_2n[,2], each = n_perms_rest)
    )
  # fill placeholders
  for (i in 1:nrow(combs_2n)) {
    rest_elements <- setdiff(2:n, combs_2n[i,])
    rest_perms <- permutations(n - 3, n - 3, v = rest_elements)
    res[1:n_perms_rest + (i-1)*n_perms_rest, 3:(n - 1)] <- rest_perms
  }
  res
}

get_perms(5)
#>       [,1] [,2] [,3] [,4] [,5]
#>  [1,]    1    2    4    5    3
#>  [2,]    1    2    5    4    3
#>  [3,]    1    2    3    5    4
#>  [4,]    1    2    5    3    4
#>  [5,]    1    2    3    4    5
#>  [6,]    1    2    4    3    5
#>  [7,]    1    3    2    5    4
#>  [8,]    1    3    5    2    4
#>  [9,]    1    3    2    4    5
#> [10,]    1    3    4    2    5
#> [11,]    1    4    2    3    5
#> [12,]    1    4    3    2    5

^{由 reprex package (v2.0.1)}

于 2021-08-28 创建

R：列出所有无方向的循环permutations/arrangements（即clockwise/anti-clockwise相同）

R: list all directionless circular permutations/arrangements (i.e. where clockwise/anti-clockwise are the same)

r

circular-permutations