Алгоритм сопоставления всех элементов с другим элементом в том же списке, где некоторые имеют ограничения

Question

Заданный массив [a, b, c, d, e, f]

Я хочу сопоставить каждую букву с любой другой буквой, кроме самой себя, в результате получится что-то вроде:

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

Подвох состоит в том, что каждая буква может быть ограничена совпадением с одной или несколькими другимибуквы.

Так, скажем, например,

• a не может быть сопоставлено с c, d
• c не может быть сопоставлено с e, f
• e не может быть сопоставлено с

Любое руководство о том, как это сделать?Я использую Ruby, но любой псевдокод будет полезен.

Спасибо!

Answer 1

Проблема, которую вы описываете, - это проблема графа, называемая максимальное совпадение (или, точнее, идеальное совпадение ).Ограничения соответствуют вершинам графа, между которыми нет линии.

Вы можете использовать алгоритм соответствия Эдмонда .

Answer 2

Давайте пока предположим, что решение существует.Это может быть не так.

• Выберите один из ваших элементов и попробуйте сопоставить его.
• Если он нарушает одно из ваших правил, попробуйте еще раз, пока не сделаете.* Выберите другой элемент и попробуйте сопоставить его.Если вы пробегаете все остальные элементы и нарушаете правило каждый раз, затем возвращаетесь, не сопоставляете свое предыдущее совпадение и попробуйте другое.
• Продолжайте, пока все ваши элементы не будут израсходованы.

  Если вы не знаете, существует ли решение или нет, вам нужно будет отслеживать ваши попытки и выяснить, когда вы их все перепробовали.Или используйте некоторую проверку в начале, чтобы увидеть, есть ли какие-либо очевидные противоречия в вашем наборе правил.

Answer 3

Я не уверен, что понимаю проблему, но это, кажется, соответствует вопросу:

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

Answer 4

$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