如何用R高效生成唯一排列？现有慢代码的优化方法求助

问题根源 #

原代码的核心问题是生成了所有全排列（包括大量重复项），再通过去重统计数量。对于包含重复元素的向量，比如l1有7个重复的"R"，总全排列数是10! = 3628800，但其中绝大多数是重复的，生成这些冗余排列完全是资源浪费，直接导致运行速度极慢。

优化方案：直接用数学公式计算 #

唯一排列数的计算公式是：
$$\text{唯一排列数} = \frac{n!}{k_1! \times k_2! \times ... \times k_m!}$$
其中：

• $n$ 是向量的总元素数
• $k_1, k_2,...,k_m$ 是每个不同元素的出现次数

实现代码 #

无需依赖combinat包，直接用R内置函数计算，完全避免生成任何排列：

library(magrittr)
library(tictoc)

count_unique_perm_optimized <- function(l = NULL) {
  elem_counts <- table(l)
  factorial(length(l)) / prod(factorial(elem_counts))
}

测试验证 #

测试输入 #

l1 <- c("R", "R", "R", "R", "R", "R", "R", "E", "K", "P") # 预期结果：720
l2 <- c("R", "R", "R", "R", "R", "Q", "G", "K", "M", "S") # 预期结果：30240

速度对比 #

# 原代码运行速度
tic()
count_unique_perm(l = l1)
toc()
# 118.155 sec elapsed

# 优化后代码运行速度
tic()
count_unique_perm_optimized(l = l1)
toc()
# 0.001 sec elapsed（实际运行时间略有波动，均为毫秒级）

tic()
count_unique_perm_optimized(l = l2)
toc()
# 0.001 sec elapsed

结果验证 #

count_unique_perm_optimized(l1)
# [1] 720
count_unique_perm_optimized(l2)
# [1] 30240

额外说明 #

如果向量元素数量很大（比如超过20），直接计算阶乘可能出现数值溢出，可改用对数计算规避：

count_unique_perm_optimized_log <- function(l = NULL) {
  elem_counts <- table(l)
  log_result <- lfactorial(length(l)) - sum(lfactorial(elem_counts))
  exp(log_result)
}

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