Algorithm for matching all items with another item in same list, where some have restrictions

Question

Given array [a, b, c, d, e, f]

I want to match each letter with any other letter except itself, resulting in something like:

• a - c
• b - f
• d - e

The catch is that each letter may be restricted to being matched with one or more of the other letters.

So let's say for example,

• a cannot be matched with c, d
• c cannot be matched with e, f
• e cannot be matched with a

Any guidance on how to go about this? I'm using Ruby, but any pseudo code would be helpful.

Thanks!

Answer 1

The problem you are describing is a graph problem called maximum matching (or more specifically perfect matching). The restrictions correspond to vertexes in the graph that do not have a line between them.

You can use Edmond's matching algorithm.

Answer 2

Let's assume for now that a solution exists. It may not.

• Pick one of your elements, and try to match it.
• If it breaks one of your rules, try again until you do.
• Choose another element, and try to match that. If you run through all other elements and break a rule each time, then go back, unmatch your previous match, and try another one.
• Continue until all of your elements are used up.

If you don't know whether a solution exists or not, then you'll need to keep track of your attempts and figure out when you've tried them all. Or, use some checking at the beginning to see if there are any obvious contradictions in your rule set.

Answer 3

$letters = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j');
$exclusions = array('a' => array('e', 'd', 'c'), 'b' => array('a','b', 'c','d')); foreach ($letters as $matching) {
foreach ($letters as $search) {
if(!in_array($search,$exclusions[$matching])){
if($search!=$matching){
$match[$matching][] = $search;
}
}
}
}
print_r($match);

The innermost EVAL could be added to the next outer one...

you can see this in action at http://craigslist.fatherstorm.com/stackoverflow2.php

Answer 4

I'm not sure I understand the problem, but this seems to fit the question:

%w[a b c d e f].combination(2).to_a - [%w[a c],%w[a d],%w[c e],%w[c f],%w[e a]]
# =>  [["a", "b"], ["a", "e"], ["a", "f"], ["b", "c"], ["b", "d"], ["b", "e"], ["b", "f"], ["c", "d"], ["d", "e"], ["d", "f"], ["e", "f"]]