将项目分组为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组分组,不会遗漏任何一个.

我制作了一个脚本,我可以通过这个小小的输入来实现这个目标,但是对于大的ammounts,它变得太慢了.

我的逻辑是:

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封面问题.每个字母都是一个节点,每一对都是一个边缘,你想要将图形划分为大小为3(三角形)的顶点不相交的集团.如果您希望分区具有最小基数,那么您需要最小集团封面.
实际上这将是一个k-clique封面问题,因为在clique封面问题中你可以拥有任意/不同大小的派系.