以 3 为一组对项目进行分组的算法

Question

我正在尝试解决一个问题，其中我有像这样的对:

A C
B F
A D
D C
F E
E B
A B
B C
E D
F D

我需要将它们分成 3 组，其中我必须从该列表中找到匹配的三角形。基本上我需要一个结果，如果它可能或不对集合进行分组。

所以可能的组是(ACD 和BFE)，或者(ABC 和DEF)和这个集合是可分组的，因为所有字母都可以分组为 3 个一组，并且没有一个被遗漏。

我制作了一个脚本，我可以在其中实现少量输入，但对于大量输入，它变得太慢了。

我的逻辑是:

make nested loop to find first match (looping untill I find a match)
 > remove 3 elements from the collection
  > run again

我一直这样做，直到我没有信件。由于可能有不同的组合，我从不同的字母开始多次运行此程序，直到找到匹配项。

我可以理解，这给我的循环顺序至少为 N^N 并且可能会变得太慢。有没有更好的逻辑来解决这些问题？这里可以用二叉树吗？

Answer 1

这个问题可以建模为图 Clique cover problem .每个字母都是一个节点，每一对都是一条边，您希望将图形划分为大小为 3(三角形)的vertex-disjoint cliques。如果您希望分区具有最小基数，那么您需要一个最小团覆盖。
实际上这将是一个 k-clique 覆盖问题，因为在 clique 覆盖问题中你可以有任意/不同大小的 cliques。