将项目分为3组的算法 [英] Algorithm to group items in groups of 3

问题描述

我正在尝试解决以下问题：

I am trying to solve a problem where I have pairs like:

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

，我需要将它们分为3组，其中我必须具有该列表中的匹配三角。基本上我需要一个结果，如果可能的话，或者不可以对一个集合进行分组。

and I need to group them in groups of 3 where I must have a triangule of matching from that list. Basically I need a result if its possible or not to group a collection.

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

So the possible groups are (ACD and BFE), or (ABC and DEF) and this collection is groupable since all letters can be grouped in groups of 3 and no one is left out.

我制作了一个脚本，可以用少量的输入来实现此目的。

I made a script where I can achieve this for small ammounts of input but for big ammounts it gets too slow.

我的逻辑是：

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

，直到我没信为止。由于可以有不同的组合，因此我会从不同的字母开始多次运行，直到找到匹配项。

and I do this until I am out of letters. Since there can be different combinations I run this multiple times starting on different letters until I find a match.

我可以理解，这至少让我循环执行 N ^ N 会变得太慢。对于此类问题是否有更好的逻辑？可以在这里使用二叉树吗？

I can understand that this gives me loops in order at least N^N and can get too slow. Is there a better logic for such problems? can a binary tree be used here?

推荐答案

此问题可以建模为图形小集团覆盖问题。每个字母都是一个节点，每对字母都是一个边，您想将图形划分为大小为3（三角形）的顶点不相交团。如果您希望分区具有最小基数，那么您想要一个最小集团覆盖率。

实际上，这将是一个k-clique覆盖率问题，因为在集团覆盖率问题中，您可以有任意大小/不同大小的小集团。

This problem can be modeled as a graph Clique cover problem. Every letter is a node and every pair is an edge and you want to partition the graph into vertex-disjoint cliques of size 3 (triangles). If you want the partitioning to be of minimum cardinality then you want a minimum clique cover.
Actually this would be a k-clique cover problem, because in the clique cover problem you can have cliques of arbitrary/different sizes.

这篇关于将项目分为3组的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！