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

Конфигуратор действительно прост. Несмотря на то, что он имеет больше функций, чем этот, его можно смоделировать как несколько «радиогрупп». (например, элемент управления пользовательского интерфейса), где должен быть выбран один из n параметров.

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

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

Я сделал наивный подход, чтобы решить эту проблему, используяПринцип включения-исключения, Однако, насколько я могу видеть, любой алгоритм, основанный на этом методе, должен работать в O (2 ^ n), который не будет работать. Есть, конечно, несколько возможных оптимизаций, которые должны обеспечить достойное время выполнения, но все еще существуют легко создаваемые сценарии наихудшего случая.

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

Update

Я понимаю, что не объяснил, как правила применяются достаточно хорошо.

Есть несколько групп с опциями. В каждой группе должен быть выбран один и только один вариант. В группе может быть один или несколько вариантов.

Существует только один тип ограничений. Если выбран вариант A в некоторой группе, тогда вариант B в некоторой другой группе не может быть выбран. Может быть любое количество ограничений, нет ограничений на количество ограничений / правил, применимых к группе опций или самой опции.

Вот пример:

Group 1:
x1 x2 x3 x4 x5

Group 2:
у1 у2 у3

Group 3:
z1 z2 z3 z4

Constraints:
x1 & lt; - & gt; у2 *
x1 & lt; - & gt; z4
y2 & lt; - & gt; z2

* Если опция x1 выбрана в группе 1, то опция y2 в группе 2 не может быть выбрана.

Используя включение-исключение, я бы рассчитал количество комбинаций как

Комбинации = Cno rules - Сr[1] - Сr[2] - Cr[3] + Cr[1,2] + Cr[1,3] + Cr[2,3] - Сr[1,2,3]

куда

Сno rules = 5 * 3 * 4

Сr[a, b, c] = Количество комбинаций, нарушающих правило a, b и c.

Метод, к сожалению, требует 2 ^ | rules | расчеты.