算法在同一列表中的其他項目，其中一些有限制

Question

鑑於陣列匹配的所有項[A，B，C，d，E，F]

欲與任何其他字母的每個字母匹配除了本身，導致類似：

• 一個 - ç
• b - ˚F
• d - 電子

美中不足的是，讓每ter可能被限制爲與一個或多個其他字母匹配。

因此，讓我們說，例如，

• 一種無法用C相匹配，d
• C不能隨e匹配，F
• E能不能用

匹配有關如何解決這個問題的任何指導？我使用Ruby，但任何僞代碼都會有所幫助。

謝謝！

Answer 1

您所描述的問題是一個圖形問題，稱爲maximum matching（或更具體地說完美匹配）。這些限制對應於圖中頂點之間沒有連線的頂點。可以使用Edmond's matching algorithm。

Answer 2

現在假設存在解決方案。它可能不會。

• 選擇一個元素，並嘗試匹配它。
• 如果它違反了你的規則之一，請再試一次，直到你做到。
• 選擇另一個元素，並嘗試與其匹配。如果你經歷了所有其他元素並且每次都違反規則，那麼返回，與之前的匹配不匹配，然後嘗試另一個匹配。
• 繼續，直到所有元素都用完。

如果您不知道解決方案是否存在，那麼您需要跟蹤您的嘗試並確定何時嘗試了所有解決方案。或者，在開始時使用一些檢查來查看規則集中是否存在任何明顯的矛盾。

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）;

最裏面的EVAL可以被添加到下一個外...

您可以在行動，在 http://craigslist.fatherstorm.com/stackoverflow2.php

Answer 4

看到這個我不知道我理解的問題，但是這似乎符合問題：

%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"]]