Меня попросили запрограммировать подпрограмму для определения количества возможных комбинаций в конфигураторе продукта.
Конфигуратор действительно прост. Несмотря на то, что он имеет больше функций, чем этот, его можно смоделировать как несколько «радиогрупп» (например, элемент управления пользовательского интерфейса), где необходимо выбрать один из n параметров.
Единственный вид ограничений, которые можно использовать, - это правила, которые говорят, что если выбран один параметр, другой параметр не может быть выбран.
Итак, я хочу рассчитать количество различных продуктов, которые можно настроить, с учетом набора групп параметров и ограничений.
Я сделал наивный подход, чтобы решить эту проблему, используя Принцип исключения-включения . Однако, насколько я вижу, любой алгоритм, основанный на этом методе, должен работать в O (2 ^ n), который не будет работать. Конечно, есть несколько возможных оптимизаций, которые должны обеспечить достойное время выполнения, но все еще существуют легко создаваемые наихудшие сценарии.
Это довольно много, где я сейчас нахожусь. Есть предложения?
Обновление
Я понимаю, что не объяснил, как правила применяются достаточно хорошо.
Есть несколько групп с опциями. В каждой группе должен быть выбран один и только один вариант. В группе может быть один или несколько вариантов.
Существует только один тип ограничений. Если выбран вариант A в какой-либо группе, то параметр B в какой-либо другой группе выбрать нельзя. Ограничений может быть любое количество, нет ограничений на количество ограничений / правил, применимых к группе параметров или к самому параметру.
Вот пример:
Группа 1:
x1 x2 x3 x4 x5
Группа 2:
у1 у2 у3
Группа 3:
z1 z2 z3 z4
Ограничения:
x1 <-> y2 *
x1 <-> z4
y2 <-> z2
* Если опция x1 выбрана в группе 1, опция y2 в группе 2 не может быть выбрана.
Используя включение-исключение, я бы рассчитал количество комбинаций как
Комбинации = C без правил - C r [1] - C r [2] - C r [3] + C r [1,2] + C r [1,3] + C r [2,3] - C r [1,2,3]
Где
C без правил = 5 * 3 * 4
C r [a, b, c] = Количество комбинаций, нарушающих правило a, b и c.
Метод, к сожалению, требует 2 ^ | rules | расчеты.