高效划分配对数据集为完备最小聚类的方法问询

给定一个偶基数集合v（例如v <- 1:6），我们先通过以下代码构建data.frame类型的df：

k <- 2
x <- rep(v, each = k)
df <- data.frame(A = x, B = c(tail(x, -(k + 1)), head(x, k + 1)))

生成的df有两个核心特点：

• 每行代表一组无重复元素的配对（pair）
• 每一列中，集合v的每个元素都恰好出现k次

聚类目标 #

需要将这些配对划分为若干聚类，每个聚类必须满足最小且完备的要求：

• 完备性：聚类必须包含v中的所有元素
• 最小性：聚类中不存在重复元素
  理想情况下，聚类的总数应为2*k。

现有方案的问题 #

目前使用的蒙特卡洛模拟方案代码如下：

out <- c()
repeat {
  if (nrow(df) == 0) {
    break
  }
  repeat {
    k <- sample.int(nrow(df), length(v) / 2)
    if (!length(setdiff(v, unlist(df[k, ])))) {
      out <- c(out, list(df[k, ]))
      df <- df[-k, ]
      break
    }
  }
}

但当集合v的基数较大时，该方法的效率极低，因此需要更稳定高效的实现方案，例如回溯法或其他更优雅的算法。

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