Рассадка людей в кинотеатре

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

Общий вопрос:

Что такое алгоритм для размещения люди в кинотеатре, так что они сидят прямо рядом со своими друзьями, но не рядом со своими врагами.

Технический вопрос:

Учитывая сетку N на M, заполните сетку N * M - 1 элементами. Каждый элемент имеет логическое значение ассоциации для каждого из других элементов N * M - 2. В каждой строке из N элементы, расположенные непосредственно рядом с другими элементами, должны иметь положительное значение ассоциации для других элементов. Столбцы, однако, не имеют значения, т. Е. Предмет может быть «врагом» с предметом перед ним. Примечание: Если элемент A имеет положительное значение ассоциации для B, это означает, что B также имеет положительное значение ассоциации для A. Это работает так же для отрицательных значений ассоциации. Гарантируется, что предмет будет иметь положительную ассоциацию хотя бы с одним другим предметом. Также у вас есть доступ ко всем элементам и их значениям связи, прежде чем вы начнете размещать их в сетке.

Комментарии:

Я исследовал эту проблему и размышлял над ней со вчерашнего дня, судя по тому, что я обнаружил, она напоминает мне проблему упаковки бункеров с некоторыми дополнительными требованиями.В свободное время попытался реализовать это, но большие группы «врагов» сидели рядом друг с другом. Я уверен, что в большинстве ситуаций придется иметь по крайней мере одну пару врагов, сидящих рядом друг с другом, но мое решение было далеко не оптимальным. На самом деле это выглядело так, как если бы я только что рандомизировал его.

Что касается моей реализации, я сделал N = 10, M = 10, количество элементов = 99 и имел массив размером 99 для КАЖДОГО элемента, который имел случайное логическое значение, которое относилось к дружбе между соответствующий номер позиции. Это означает, что каждый предмет имел ценность дружбы, которая соответствовала и самому себе, я просто проигнорировал эту ценность.

Я планирую повторить эту попытку позже и опубликую код. Может ли кто-нибудь придумать "хороший" способ сделать это, чтобы минимизировать столкновения между врагами из-за сидения?