Algorithm to group items in groups of 3
algorithm, combinatorics
Solution
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.
Problem
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 ``` 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. 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. My logic is: ``` 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. 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?