I'm looking for an algorithm that given a set of number pairs as below, can pair them in such a way that each group contains four unique numbers ie [1,2,3,4]
Any ideas?
[1, 2]
[1, 3]
[1, 4]
[1, 5]
[2, 3]
[2, 4]
[2, 5]
[3, 4]
[3, 5]
[4, 5]
Algorithm for joining pairs
Viewed 71
1 Answers
You can think of this as a maximum matching problem. In the maximum matching problem, you have a collection of items (nodes) and possible links between them (edges). The goal is to pair off the items using only the possible links so that as many items as possible are paired off.
In your case, your items are the pairs, and you'd say that two pairs can be linked if they have no numbers in common.
Once you've set things up this way, you can use an off-the-shelf solver for maximum matching to find the optimal pairing. Python's networkx package has the support to do this, for example.
Hope this helps!
Related