r - R:列出所有无方向的圆形排列/排列(即顺时针/逆时针相同)
问题描述
如何列出 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(2, 1, 3, 4)
(c(3, 1, 2, 4)
即输出中的第 3 和第 5 个条目)?仅仅是拿前半部分结果的情况吗?
有没有更可靠的方法来做到这一点?非常感谢您回答我的问题或提供建议。
解决方案
我们不能简单地获取结果的前半部分permutations(n-1, n-1)
并附加 n。这在 n = 5 时很容易看出。
我建议使用以下方法:
- 我们将第一个元素设置为始终为 1。这样,我们确保对每组等效排列仅采用 1 个排列。这与您将 4 the always 作为示例中的最后一个元素所做的基本相同。
- 仅考虑元素#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 包于 2021-08-28 创建(v2.0.1)
推荐阅读
- node.js - 检查用户是否在 Express 中打开了静态文件?
- kubernetes - 在 Kubernetes 集群的所有节点上运行守护程序集
- python - Jupyter notebook 内核未连接 StreamClosedError
- javascript - 如何使用 Javascript、jQuery 对提交按钮应用多个操作?
- rest - 使用 Kotlin 协程的 Guava LoadingCache
- c# - 需要从 UWP 使用智能卡上的私钥解密 smime p7m 文件
- java - Mapreduce不同的key产生不同数量的消息
- python-2.7 - 如何导入 Python 模块并对其依赖项进行猴子补丁?
- javascript - 将数据从表更新到数据库?
- laravel-backpack - 错误 403 禁止。此操作未经授权