如何有效地将对分成簇，以便每个簇包含给定集合的所有条目

Question

假设我们有一个偶数基数的集合

v

，例如

v <- 1:6

，以及一个由

df

条目组成的 data.frame

v

，它是由

v

中每个元素的固定出现次数定义的每列，即

k

，例如

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

如图所示

> df
   A B
1  1 2
2  1 3
3  2 3
4  2 4
5  3 4
6  3 5
7  4 5
8  4 6
9  5 6
10 5 1
11 6 1
12 6 2

其中

1:6

在两列上出现的次数为

2

> table(df$A)

1 2 3 4 5 6
2 2 2 2 2 2

> table(df$B)

1 2 3 4 5 6
2 2 2 2 2 2 

目标和预期产出

在

df

中，每一行代表一个“对”，并且不存在重复的“对”。我想知道如何将这些对分成簇，使得每个簇都是最小和完整，即每个簇包含来自

v

，的所有值，没有任何重复的条目。

由于

v

的基数是

length(v)

，并且

df

中每个条目的出现次数实际上是

2*k

，因此通过

df

的“理想”分割得到的簇数应该是

2*k*length(v)/length(v) == 2*k

。换句话说，簇的数量仅由

k

定义，例如

2*k

。

例如，

df

可以分为如下所示的

4

簇，其中可以实现“完整性”属性

[[1]]
  A B
1 1 2
5 3 4
9 5 6

[[2]]
   A B
2  1 3
7  4 5
12 6 2

[[3]]
   A B
3  2 3
8  4 6
10 5 1

[[4]]
   A B
4  2 4
6  3 5
11 6 1

请注意，上面的输出只是有效实例之一，应该还有其他候选实例进行聚类。

问题

一种可能的解决方案是使用蒙特卡罗模拟，如果随机聚类满足所有约束，则迭代地保持有效的聚类结果。代码可能如下所示

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
    }
  }
}

有时可以给出所需的输出，例如

> out
[[1]]
   A B
6  3 5
11 6 1
4  2 4

[[2]]
   A B
2  1 3
7  4 5
12 6 2

[[3]]
   A B
8  4 6
3  2 3
10 5 1

[[4]]
  A B
1 1 2
9 5 6
5 3 4

但是，这种方法有两个主要问题：

1. 不稳定：由于簇是顺序生成的（或者，我们可以说它是以“贪婪”的方式实现的），因此如果先前生成的簇不能总是保证找到下一个随机簇的可行性已用完可能的对。然后代码陷入无限循环..

2. 效率低：如果集合

   v

   有很大的基数，蒙特卡罗模拟的空间会呈指数增长，这会大大减慢寻找有效解决方案的过程。

---

我想知道是否有一个稳定且更高效的方法来解决此类问题。我认为 回溯 应该有效，但我相信一定有其他方法可以以更优雅的方式实现它。

期待多样化、有趣的解决方案。提前感谢！