在R中生成n个元素划分为m个非空子集的所有分法

你需要的是生成所有满足以下条件的长度为m的正整数序列：

• 每个元素 ≥1
• 所有元素之和等于n
• m < n

这类序列对应n的m部有序分拆（若子集有区分度，比如不同子集对应不同组别），数量为组合数C(n-1, m-1)；如果子集无区分度，需对序列去重，对应第二类斯特林数计数的无序划分。以下是具体实现方案：

1. 基础R实现（无需额外包） #

通过递归方法生成所有符合条件的有序序列，适合小n场景：

generate_partition_sequences <- function(n, m) {
  if (m > n) stop("m必须小于等于n")
  if (m == 1) return(matrix(n, nrow = 1, dimnames = list(NULL, "n1")))
  
  # 递归生成所有可能的序列
  recurse <- function(remaining, k) {
    if (k == 1) return(matrix(remaining, nrow = 1))
    lapply(1:(remaining - k + 1), function(x) {
      cbind(x, recurse(remaining - x, k - 1))
    }) %>% do.call(rbind, .)
  }
  
  result <- recurse(n, m)
  colnames(result) <- paste0("n", 1:m)
  result
}

# 示例：生成n=4，m=2的所有有序序列
generate_partition_sequences(4, 2)
#      n1 n2
# [1,]  1  3
# [2,]  2  2
# [3,]  3  1

2. 用现成包快速实现 #

partitions包中的compositions()函数可直接生成有序分拆，效率更高：

# 安装并加载包
install.packages("partitions")
library(partitions)

# 生成n=4，m=2的有序分拆（每列为一个序列，转置后每行一个序列）
t(compositions(4, m = 2))
#      [,1] [,2]
# [1,]    1    3
# [2,]    2    2
# [3,]    3    1

3. 生成无序划分的大小序列 #

如果子集无区分度（即(1,3)和(3,1)视为同一种划分），可对有序序列排序后去重：

generate_unordered_partitions <- function(n, m) {
  seq_matrix <- generate_partition_sequences(n, m)
  # 对每行排序
  sorted_seqs <- t(apply(seq_matrix, 1, sort))
  # 去重得到无序划分
  unique(sorted_seqs)
}

# 示例：生成n=4，m=2的无序划分
generate_unordered_partitions(4, 2)
#      [,1] [,2]
# [1,]    1    3
# [2,]    2    2

注意事项 #

• 这类序列的数量随n和m增长极快：有序分拆数量为choose(n-1, m-1)，无序划分数量为第二类斯特林数Stirling2(n, m)，仅适合n较小的模拟场景（比如n≤10）。

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