鑑於陣列匹配的所有項[A,B,C,d,E,F]算法在同一列表中的其他項目,其中一些有限制
欲與任何其他字母的每個字母匹配除了本身,導致類似:
- 一個 - ç
- b - ˚F
- d - 電子
美中不足的是,讓每ter可能被限制爲與一個或多個其他字母匹配。
因此,讓我們說,例如,
- 一種無法用C相匹配,d
- C不能隨e匹配,F
- E能不能用
匹配有關如何解決這個問題的任何指導?我使用Ruby,但任何僞代碼都會有所幫助。
謝謝!
鑑於陣列匹配的所有項[A,B,C,d,E,F]算法在同一列表中的其他項目,其中一些有限制
欲與任何其他字母的每個字母匹配除了本身,導致類似:
美中不足的是,讓每ter可能被限制爲與一個或多個其他字母匹配。
因此,讓我們說,例如,
匹配有關如何解決這個問題的任何指導?我使用Ruby,但任何僞代碼都會有所幫助。
謝謝!
您所描述的問題是一個圖形問題,稱爲maximum matching(或更具體地說完美匹配)。這些限制對應於圖中頂點之間沒有連線的頂點。可以使用Edmond's matching algorithm。
現在假設存在解決方案。它可能不會。
如果您不知道解決方案是否存在,那麼您需要跟蹤您的嘗試並確定何時嘗試了所有解決方案。或者,在開始時使用一些檢查來查看規則集中是否存在任何明顯的矛盾。
$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
這似乎並不匹配每個字母與另一個字母,而是它只是從現有的數組,但不包括指定的字母數組。 – 99miles 2010-10-26 21:28:58
正確...所以,你有每個項目和每個其他字母,它可以匹配符合條件(不是本身+不在排除列表本身)之後,它是一個顯示問題,因爲你有你需要的數據........ – FatherStorm 2010-10-28 21:57:10
看到這個我不知道我理解的問題,但是這似乎符合問題:
%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"]]
哎呀,這看起來很沉重!雖然謝謝! – 99miles 2010-10-26 21:53:16