如何在R中生成不计方向的无向环形排列/置换的通用实现方法

R生成不计方向无向环形排列的实现方案 #

问题说明 #

我们需要生成不计旋转、不计顺时针/逆时针方向的无向环形排列，即两种排列如果可以通过旋转或翻转重合则视为同一类。以1:4为例，最终符合要求的排列总数应为$\frac{(4-1)!}{2}=3$种。

直接截取前半部分是否可行？ #

不可行。这种方法完全依赖排列生成的顺序，一旦gtools::permutations的生成规则调整、或者你切换了其他排列生成工具，截取前半部分的结果就会出错，稳定性极差，不推荐使用。

稳妥的通用实现方法 #

核心思路分两步消除等价重复：

1. 消除旋转等价：固定一个元素的位置（比如固定第一个元素为输入向量的第一个值），因为所有环形排列都可以通过旋转把该元素转到固定位置，直接过滤掉所有旋转重复的排列。
2. 消除方向等价：对于剩余元素的排列，仅保留「第二个非固定元素 < 最后一个非固定元素」的排列。因为互为逆序的两个排列，翻转后这两个位置的数值大小关系会反过来，通过该规则可以刚好保留一类、过滤一类，不会有重复或遗漏。

通用代码实现

library(gtools)

# 输入参数x为待生成排列的向量
undirected_circular_perm <- function(x) {
  n <- length(x)
  # 长度小于等于2时只有1种无向环形排列
  if (n <= 2) {
    return(matrix(x, nrow = 1, dimnames = NULL))
  }
  # 固定第一个元素，消除旋转重复
  fixed_val <- x[1]
  rest_vals <- x[-1]
  # 生成剩余元素的全排列
  rest_perms <- permutations(n = n-1, r = n-1, v = rest_vals)
  # 过滤逆序重复，仅保留第二个非固定元素小于最后一个非固定元素的排列
  keep_idx <- rest_perms[, 1] < rest_perms[, ncol(rest_perms)]
  # 拼接固定元素得到最终结果
  res <- cbind(fixed_val, rest_perms[keep_idx, ])
  colnames(res) <- NULL
  return(res)
}

测试示例

以1:4为输入测试：

undirected_circular_perm(1:4)

输出结果为：

[,1] [,2] [,3] [,4]
[1,]    1    2    3    4
[2,]    1    2    4    3
[3,]    1    3    2    4

完全符合要求，没有重复也没有遗漏。

内容的提问来源于stack exchange，提问作者user3236841