Количество комбинаций в конфигураторе

https://stackoverflow.com/questions/1154565

18-09-2019
|

Вопрос

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

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

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

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

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

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

Обновить

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

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

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

Таким образом, примером может быть:

Группа 1:
x1 x2 x3 x4 x5

Группа 2:
y1 y2 y3

Группа 3:
z1 z2 z3 z4

Ограничения:
x1 <-> y2 *
x1 <-> z4
y2 <-> z2

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

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

Комбинации = C_{никаких правил} - С_r[1] - С_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^|правил| вычислений.

Решение

Хорошо, я не могу обойти 2 ^ N, но я могу уменьшить набор выборок.Чтобы сделать это, мы вычислим "Составленные ограничения".Составное ограничение - это ограничение, при котором, если выбран параметр "все параметры с левой стороны", то ни один из параметров с правой стороны не может быть выбран, но никакое другое ограничение, основанное на параметрах с левой стороны, не может применяться.

Нам нужно вычислить набор всех возможных Составных ограничений из набора ограничений.Хотя в этом нет необходимости, мы "исправим" существующие ограничения, поменяв местами левую и правую руки, если группа правой руки меньше группы левой.Это может уменьшить некоторые составные ограничения, хотя для замены возможны лучшие эвристические методы.

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

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

Зафиксируйте ограничения таким образом, чтобы группа левой руки была меньше или равна группе правой руки.
Составьте ограничения:
1. Сортировка ограничений по левой стороне
2. Последовательно, для каждого ограничения:
  1. Сложите ограничитель со всеми ограничителями, которые следуют за ним, той же левой рукой, поворачивая x1 <-> y1, x1 <-> y2 ... x1 <-> yN в Set(x1) <-> Set(y1 ... yN)
  2. Составьте свернутое ограничение с каждым уже свернутым ограничением, если:
    - x1 не находится в правой части уже свернутого ограничения
    - x1 не входит в ту же группу ни одного элемента в левой руке
  3. Добавьте свернутое ограничение и все его композиции к набору свернутых ограничений
Вычислите Минимальный набор, взяв все параметры и удалив те, которые отображаются в левой части фиксированных ограничений.

Теперь вы можете вычислить количество комбинаций с помощью приведенной ниже формулы.Давайте назовем CC составным ограничением.Тогда количество комбинаций равно:

C(Mininum Set) + CCC1 + ... + CCCn

Где:

C (Минимальный набор) - это количество комбинаций, возможных при минимальном наборе.
CCCx - это количество комбинаций, возможных путем взятия минимального набора, замены любых групп, для которых есть опция в левой части CCx, на эту опцию, а затем удаления всех опций в правой части CCx.

Обратите внимание, что выражение является чисто аддитивным.Это означает, что для того, чтобы это выражение дало ожидаемый результат, должны быть выполнены следующие два условия:

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

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

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

Для второго доказательства обратите внимание, что набор CCS содержит, по определению, все допустимые комбинации для опций слева.

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

Поскольку набор CCS содержит все допустимые комбинации для левой руки, то существует один CC с теми же параметрами для левой руки.Следовательно, в этой комбинации должна быть опция, которая не включена ни в одну комбинацию для этого CC.Но единственные параметры, не включенные в эту CC, - это те, которые отображаются слева для других CCS, и те, которые должны быть исключены из нее с помощью ограничений.Поскольку ни то, ни другое не может быть таковым, то такая комбинация не может существовать.

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

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

И на этом доказательство заканчивается.

Давайте посмотрим, как это применимо, на примере из комментариев:

G1: x1, x2, x3 
G2: y1, y2 
G3: z1, z2, z3 

R1: x1 <-> y2 
R2: x3 <-> y2 
R3: y1 <-> z1 
R4: y2 <-> z2 
R5: y2 <-> z3

CC1: {x1} <-> {y2}
CC2: {x3} <-> {y2}
CC3: {y1} <-> {z1}
CC4: {x1, y1} <-> {y2, z1}
CC5: {x3, y1} <-> {y2, z1}
CC6: {y2} <-> {z2, z3}

Давайте кратко поразмышляем о составных группах, которых нет в списке:

R1&R2: {x1, x3} <-> {y2} -- not in the list because x1 and x3 belongs to the same
                            group
R1&R5: {x1, y2} <-> {y2} -- not in the list because the left hand of R2, y2
                            appears in the right hand of R1

Теперь давайте посмотрим, какие варианты возможны в каждом наборе:

Minimum Set: (x2), (), (z1, z2, z3)    
CC1: (x1), (), (z1, z2, z3) -- replace G1 with x1, remove y2 from G2
CC2: (x3), (), (z1, z2, z3) -- replace G1 with x3, remove y2 from G2
CC3: (x2), (y1), (z2, z3)   -- replace G2 with y1, remove z1 from G3
CC4: (x1), (y1), (z2, z3)   -- replace G1 with x1, G2 with y1, remove y2 and z1
CC5: (x3), (y1), (z2, z3)   -- replace G1 with x3, G2 with y1, remove y2 and z1
CC6: (x2), (y2), (z1)       -- replace G2 with y2, remove z2 and z3 from G3

Теперь давайте все сложим:

C(Minimum Set) = 1 * 0 *3 = 0
CCC1 = 1 * 0 * 3 = 0
CCC2 = 1 * 0 * 3 = 0
CCC3 = 1 * 1 * 2 = 2
CCC4 = 1 * 1 * 2 = 2
CCC5 = 1 * 1 * 2 = 2
CCC6 = 1 * 1 * 1 = 1

C(Minimum Set) + CCC1 + CCC2  + CCC3 + CCC4 + CCC5 + CCC6
0              + 0    + 0     + 2    + 2    + 2    + 1    = 7

Я добавлю здесь еще одну мысль.Несмотря на то, что для 5 правил имеется всего 6 CCCS, что намного меньше ожидаемых в противном случае 32 терминов, эти CCCS вычисляются с наихудшим временем 2 ^ N, поскольку для каждого правила вы должны сравнить и объединить его со всеми CCCS, созданными на данный момент.Вы можете думать о них как о двоичных числах, где бит устанавливается, если правило комбинируется, и не устанавливается, если нет.

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

Как показывает этот конкретный пример, среднее время может быть намного лучше, чем 2 ^ N.

Альтернативные алгоритмы и соображения

Ходят слухи о том, что будут ходить 2-SAT и 3-SAT.Мне кажется, что это проблема 2-SAT, в том смысле, что каждое ограничение <-> b на самом деле является предложением "!a || !b".Таким образом, все ограничения вместе могут быть просто записаны как "(!x1 || !y2) && (!x1 || !z4) && (!y2 && !z3)" и т.д.Это означает, что вы можете "решить" эту проблему в том смысле, что вы можете узнать, есть ли логическое присвоение для каждого параметра, которое сделает это истинным.Для этого существует линейный алгоритм Асполла, Пласса и Тарьяна со слайд-презентацией здесь.

Но зная, могут ли ограничения быть решены или нет это не то, о чем просили.То, что было задано, является число из способов, которыми все параметры могут быть установлены при сохранении проблемы 2-SAT true.

Теперь существуют эффективные алгоритмы для подсчета количества способов решения задачи 2-SAT.Например, этот документ представляет алгоритм, который выполняется в 1.2561ⁿ.Но даже это это нам не поможет, так как нам нужно знать что решения должны быть способны вычислять количество комбинаций, которые удовлетворяют этому решению.

Согласно Википедии, этот документ имеет алгоритм, который эффективно перечисляет все решения, что нам и нужно.Но если подсчет уже экспоненциальный, то будет и перечисление.Лучше, чем 2ⁿ, возможно, но все еще экспоненциальный.

Если мы перечислим все решения задачи 2-SAT, количество комбинаций для каждой группы будет равно 1, умноженному на количество свободных вариантов, вариантов, которые не фигурируют ни в одном ограничении, каждой группы, для которой решением не был выбран ни один вариант.

Например, взяв предыдущий набор групп и ограничений.Проблема 2-SAT, включая взаимное исключение, заключается в:

(!x1 || !y2) && (!x3 || !y2) && (!y1 || !z1) && (!y2 || !z2) && (!y2 || !z3) && (!x1 || !x3) && (!y1 || !y2) && (!z1 || !z2) && (!z1 || !z3) && (!z2 || !z3)

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

Решениями этой проблемы 2-SAT являются:

x1    x3    y1    y2    z1    z2    z3    Combinations
true  false true  false false true  false 1
true  false true  false false false true  1
true  false true  false false false false 0
true  false false false true  false false 0
true  false false false false true  false 0
true  false false false false false true  0
true  false false false false false false 0
false true  true  false false true  false 1
false true  true  false false false true  1
false true  true  false false false false 0
false true  false false true  false false 0
false true  false false false true  false 0
false true  false false false false true  0
false true  false false false false false 0
false false true  false false true  false 1
false false true  false false false true  1
false false true  false false false false 0
false false false true  true  false false 1
false false false true  false false false 0
false false false false true  false false 0
false false false false false true  false 0
false false false false false false true  0
false false false false false false false 0

В первых двух решениях нет групп без выбранной опции, поэтому количество комбинаций равно 1.В третьем решении для группы G3 не выбран параметр, поэтому мы умножаем 1 на 0.В строках, начинающихся с "false false", для группы G1 не выбрано ни одного параметра, а есть один свободный вариант:х2.Таким образом, мы умножаем 1 на 1 для них и на 0, если для G2 или G3 не выбраны опции (в этом случае количество свободных опций равно 0).

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

x₁ || x₂ || x₃ (для группы x с параметрами x₁ ..x₃)
(!x₁ || !x₂) && (!x₁ || !x₃) && (!x₂ || !x₃)

Более позднее ограничение - 2-SAT, первое - 3-SAT для любого нетривиального случая.Как это бывает, я не применяю первое ограничение, но затем количество становится равным 0.Алгоритм подсчета должен выглядеть следующим образом:

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

Таким образом, для каждой группы, в которой существует хотя бы один вариант без ограничений, выбор является неявным и анонимным.Для каждой группы, в которой все опции являются частью некоторого ограничения, если ни одна опция не была выбрана, то количество для этой группы становится равным 0, и, следовательно, количество комбинаций для этого решения также становится равным 0.

Это похоже на обман проблемы из-за допустимого ограничения > 2-SAT.В конце концов, если бы это было возможно, то проблему 3-SAT можно было бы решить, просто перечислив решения для ее части 2-SAT, а затем отбросив каждое, которое не удовлетворяет ее части 3-SAT.Увы, есть одно фундаментальное отличие, которое я могу выделить:

Все предикаты, не решенные в рамках 2-SAT части задачи, свободны от каких-либо дополнительных ограничений.

Учитывая это довольно строгое ограничение на предложения, мы можем решить эту проблему, перечислив решения для явных ограничений 2-SAT.

Если кто-то хочет продолжить в этом направлении, вперед.Я удовлетворен улучшением на 2ⁿ решение, которое я предложил.

Другие советы

Если у вас есть N группы опций, каждая с Xi варианты (0<=i<N) затем

X0*X1*...*X(N-1)

Дает вам ответ, который вы хотите.Другими словами, умножьте размер каждой группы опций.

Если у вас есть n параметры с Ci возможные значения для каждого параметра и m ограничения, верхняя граница для количества конфигураций следующая (игнорируя ограничения).

N0 = C1 * C2 * ... * Cn

Единственное ограничение вида ci == x => cj != y запрещает следующее количество конфигураций.

        N
Dk = -------
     Ci * Cj

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

N = prod(Ci, i = 1...n) * (1 - sum(1 / (Cxj * Cyj), j = 1...m))

Здесь xj и yj являются ли оба параметра индексами из j-го ограничения.

Пример

Parameters    n = 4

Parameter 1   C1 = 4   0 1 2 3 
Parameter 2   C2 = 3   4 5 6 
Parameter 3   C3 = 2   X Y
Parameter 4   C4 = 3   7 8 9

Constraints   m = 2

Constraint 1  c2 == 4 => c3 != X
Constraint 2  c3 == X => c4 != 9

N0 = 4 * 3 * 2 * 3 = 72

D1 = 72 / (3 * 2) = 12
D2 = 72 / (2 * 3) = 12

N = 72 - (12 + 12) = 48

Обновить

Я думаю, что это еще не полностью правильно, потому что это не учитывает зависимости ограничений.

~~Здесь нет коротких путей для общего случая.~~ Все не так плохо, как ты думаешь.Смотрите раздел "Переосмысление" ниже.

Действительно ли 2 ^ n так уж плохо?О скольких правилах исключения мы здесь говорим?На самом деле вам нужно сделать это только один раз для каждого конфигуратора, если только набор правил / опций не постоянно меняется на лету и не требует динамического пересчета.Если существует действительно огромное количество правил, то я бы не стал искать точное решение - рассмотрите только пересечения k-го порядка и скажите "количество комбинаций равно как минимум / большинству ...".Могут существовать другие методы просеивания, которые позволят вам быстро определить границы ответа.

Также имейте в виду:если вы учитываете только исключения, которые вам действительно нужны, то 2 ^ n - это просто верхняя граница, и ваше фактическое количество вычислений может быть значительно меньше для любых реальных сценариев.То есть, если C[1,2] равно нулю, то и C[1,2,...] тоже.Подумайте об этом:для каждого ограничения "объедините" наборы ограничений вместе, если у них есть какие-либо общие параметры.Ясно, что ваше реальное время выполнения будет определяться размером самого большого "сгустка" (который, да, может быть таким же большим, как n).

Переосмысление:C[x, y] будет равен нулю в большинство случаи.Ограничение может перекрываться только с другими ограничениями, включающими другой Группа.Другими словами, (x1<->y1) может перекрываться только с (x1<->z1) или (y1<->z2) или что-то еще, а не (x1<->y2).Аналогично, набор ограничений может перекрываться только с новой группой:в комбинация из (x1<->y1) с помощью (y1<-> z2) не взаимодействует с (x3<->z2) (группа x уже зафиксирована на x1).Вам нужно только рассмотреть включение / исключение, когда каждое правило, которое вы добавляете в комбинацию, добавляет к ней ранее не затронутую группу.Итак, вы на самом деле O (2^G), где G - количество групп (а также, возможно, другая граница, основанная на размере групп).Гораздо более управляемый!

Редактировать

Этот алгоритм неверен.Я представил альтернативный ответ в другом сообщении, который по-прежнему равен 2 ^ N в худшем случае, но в противном случае может дать лучшие результаты.

Это работает в выбранном примере, потому что y2 является частью набора исключений x1, а два первых ограничения основаны на x1.Тем не менее, теперь я вижу, что нужно сделать.Это все еще близко к 2 ^ N, но есть оптимизации, которые могут привести к значительному выигрышу.

Чтобы исправить этот алгоритм, составленные правила должны иметь вид set(ox) <-> установить (oy).Чтобы составить их, для каждого ограничения с помощью left-hand oX, которое вы сочиняете, вы также создаете другие композиции из него с каждым правилом, которое вы уже сочинили, если oX не является частью правой части составленного правила, и его группа не совпадает с левой частью группы.

Для полностью независимых ограничений это равно 2^N.В противном случае вы уменьшаете N, выполняя:

объединение ограничений с помощью общего левого
не вычисляя комбинации правил, которые являются взаимоисключающими, это делится на:
- не объединять правила для параметров в одной группе
- не комбинирующие правила, при которых левая сторона одного появляется на правой стороне другого

Я не думаю, что исправление этого алгоритма того стоит.Это довольно объемный ответ, и он будет иметь тот же порядок, что и мой альтернативный ответ, который намного легче.

Конечное редактирование

Давайте изменим это к лучшему.Как насчет этого для алгоритма:

Исправьте правила по мере необходимости, чтобы гарантировать, что для правила o1 <-> o2, group(o1) < group(o2)
Вычислите "составленные" правила, сложив все правила oX <-> o? в единое правило oX <-> Set(o?)
Вычислите "чистый" набор групп, удалив из них левую опцию каждого правила
Вычислите альтернативные наборы из чистого набора, по одному для каждого составленного правила, заменив группу левого параметра самим левым параметром и вычтя из других групп параметры правой части правила.
Для каждого набора групп вычислите количество комбинаций путем умножения количества опций в каждой группе набора.
Добавьте все результаты, полученные на шаге 5.

Давайте посмотрим на это в действии:

Group 1:
x1 x2 x3 x4 x5

Group 2:
y1 y2 y3

Group 3:
z1 z2 z3 z4

Constraints (already fixed):
x1 <-> y2 *
x1 <-> z4
y2 <-> z2

Composed rules:
x1 <-> (y2, z4)
y2 <-> (z2)

Clean set of groups:
x2x3x4x5, y1y3, z1z2z3z4

Alternate sets:
x1, y1y3, z1z2z3 (first composed rule)
x2x3x4x5, y2, z1z3z4 (second composed rule)

Totals:
4 * 2 * 4 = 32
1 * 2 * 3 = 6
4 * 1 * 3 = 12

Total: 50

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

c(no rules) = 60
c1 => 4
c2 => 3
c3 => 5
c12 => 1
c13 => 1
c23 => 0
c123 => 0

c(no rules) - c1 - c2 - c3 + c12 + c13 + c23 - c123 = 50

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

Вот его реализация на Scala:

case class GroupOption(id: Int, option: Int)
case class Group(id: Int, options: Set[Int])
case class Rule(op1: GroupOption, op2: GroupOption)
case class ComposedRule(op: GroupOption, set: Set[GroupOption])

object ComputeCombinations {
  def fixRules(rules: Set[Rule]) = {
    rules map (rule => if (rule.op1.id > rule.op2.id) Rule(rule.op2, rule.op1) else rule)
  }

  def ruledOptions(id: Int, rules: Set[Rule]): Set[Int] = (
    rules 
    filter (rule => rule.op1.id == id)
    map (rule => rule.op1.option)
  )

  def cleanseSet(groups: Set[Group], rules: Set[Rule]) = {
    groups map (group => 
      Group(group.id, group.options -- ruledOptions(group.id, rules)))
  }

  def composeRules(rules: Set[Rule]): Set[ComposedRule] = Set(
    (
      rules.toList
      sort (_.op1.id < _.op1.id)
      foldLeft (List[ComposedRule]())
      ) { (list, rule) => list match {
        case ComposedRule(option, set) :: tail if option == rule.op1 =>
          ComposedRule(option, set + rule.op2) :: tail
        case _ => ComposedRule(rule.op1, Set(rule.op2)) :: list
      }} : _*
  )

  def subset(groups: Set[Group], composedRule: ComposedRule) = (
    groups
    filter (_.id != composedRule.op.id)
    map (group => Group(group.id, group.options -- 
                                  (composedRule.set 
                                   filter (_.id == group.id)
                                   map (_.option)
                                  )))
  )

  def subsets(groups: Set[Group], composedRules: Set[ComposedRule]) = (
    composedRules map (composedRule => subset(groups, composedRule))
  )

  def combinations(groups: Set[Group]) = (
    groups.toList map (_.options.size) reduceLeft (_*_)
  )

  def allCombinations(groups: Set[Group], rules: Set[Rule]) = {
    val fixedRules = fixRules(rules)
    val composedRules = composeRules(fixedRules)
    val cleanSet = cleanseSet(groups, fixedRules)
    val otherSets = subsets(cleanSet, composedRules)
    val allSets = otherSets + cleanSet
    val totalCombinations = allSets.toList map (set => combinations(set)) reduceLeft (_+_)
    totalCombinations
  }
}

object TestCombinations {
  val groups = Set(Group(1, Set(1, 2, 3, 4, 5)),
                   Group(2, Set(1, 2, 3)),
                   Group(3, Set(1, 2, 3, 4)))
  val rules = Set(Rule(GroupOption(1, 1), GroupOption(2, 2)),
                  Rule(GroupOption(1, 1), GroupOption(3, 4)),
                  Rule(GroupOption(2, 2), GroupOption(3, 2)))
  def test = ComputeCombinations.allCombinations(groups, rules)
}

Возможно, это не совсем полезный ответ, поэтому не стесняйтесь игнорировать его...однако;В настоящее время я сам работаю над аналогичной системой;и , откровенно говоря кроме как для тривиальных примеров Я не уверен, что полезно пытаться вычислить количество допустимых комбинаций.В качестве примера, модели, над которыми я работаю в данный момент, содержат (например) 18000 элементов-кандидатов, распределенных по более чем 80 выборкам, некоторые с одним выбором / некоторые с несколькими.Помимо самых маленьких моделей, нет выгода зная число, поскольку вы просто никогда бы не записали его как полную таблицу истинности;ты в значительной степени вынужденный для выполнения правил (т.е.удалите все, что больше не является допустимым, автоматически выберите что-либо подходящее и убедитесь, что никакие правила не нарушены) по требованию.Что не обязательно является проблемой;мой текущий код обрабатывает эту модель (как веб-сервис) за ~ 450 мс, и большая часть этого времени фактически затрачивается на обработку xml для ввода / вывода.Если бы ввод / вывод не был xml, я думаю, это было бы ~ 150 мс, что круто.

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

Разве это не будет просто x ^ n, где n - количество вариантов, а x - количество вариантов для каждого варианта?

Я думаю, что Зак думает в правильном направлении.Глядя на ваше выражение для количества комбинаций, вы видите, что члены второго порядка Cr[i, j] намного меньше, чем члены C [k].Представьте себе куб, где каждая ось представляет собой группу параметров.Каждая точка в кубе представляет определенную комбинацию параметров.Поправка C [k] первого порядка исключает строку параметров между двумя поверхностями куба.Коррекция второго порядка C[i,j] происходит только тогда, когда две такие линии пересекаются в одной точке (комбинация опций) в пространстве куба.Таким образом, независимо от количества имеющихся у вас групп, поправки более высокого порядка всегда становятся все меньше.Если вы будете придерживаться

Комбинации = C (без правил) - Cr[1] - Cr[2] - Cr[3]

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

Комментарий к Сообщение Дэниела:

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

Например, рассмотрим такой случай:

Group 1:
a1 a2 a3 a4 a5

Group 2:
b1 b2 b3

Group 3:
c1 c2 c3 c4

Group 4:
d1 d2 d3 d4 d5

Rules:
a1 <-> b2
a1 <-> c2
b2 <-> c2
b2 <-> d1
a2 <-> d2

Я настроил свой базовый алгоритм просеивания с помощью этой конфигурации и получил следующие результаты (227 комбинации):

Without rules => 300
Rules: [1] => 20
Rules: [2] => 15
Rules: [3] => 25
Rules: [4] => 20
Rules: [5] => 12
Order: 1 => 208 (diff: -92)
Rules: [1, 2] => 5
Rules: [1, 3] => 5
Rules: [2, 3] => 5
Rules: [1, 4] => 4
Rules: [2, 4] => 1
Rules: [3, 4] => 5
Rules: [1, 5] => 0
Rules: [2, 5] => 0
Rules: [3, 5] => 1
Rules: [4, 5] => 0
Order: 2 => 234 (diff: 26)
Rules: [1, 2, 3] => 5
Rules: [1, 2, 4] => 1
Rules: [1, 3, 4] => 1
Rules: [2, 3, 4] => 1
Rules: [1, 2, 5] => 0
Rules: [1, 3, 5] => 0
Rules: [2, 3, 5] => 0
Rules: [1, 4, 5] => 0
Rules: [2, 4, 5] => 0
Rules: [3, 4, 5] => 0
Order: 3 => 226 (diff: -8)
Rules: [1, 2, 3, 4] => 1
Rules: [1, 2, 3, 5] => 0
Rules: [1, 2, 4, 5] => 0
Rules: [1, 3, 4, 5] => 0
Rules: [2, 3, 4, 5] => 0
Order: 4 => 227 (diff: 1)
Rules: [1, 2, 3, 4, 5] => 0
Order: 5 => 227 (diff: 0)

***Combinations: 227***

Однако, используя этот код в scala:

  val groups = Set(Group(1, Set(1, 2, 3, 4, 5)),
                   Group(2, Set(1, 2, 3)),
                   Group(3, Set(1, 2, 3, 4)),
                   Group(4, Set(1, 2, 3, 4, 5)))

  val rules = Set(Rule(GroupOption(1, 1), GroupOption(2, 2)),
                  Rule(GroupOption(1, 1), GroupOption(3, 2)),
                  Rule(GroupOption(2, 2), GroupOption(3, 2)),
                  Rule(GroupOption(2, 2), GroupOption(4, 1)),
                  Rule(GroupOption(1, 2), GroupOption(4, 2)))

Я получил ответ 258.

Я проверил вычисления методом сита, и они кажутся правильными.Возможно, можно исправить ваш алгоритм?Я действительно не могу понять, в чем дело.

Ваша проблема довольно неосуществима.

Подсчет количества решений является #P-завершенным, даже если вы ограничиваете каждую группу радиобоксов двумя вариантами
Проверка, есть ли КАКОЙ-ЛИБО выбор опций, согласующихся с ограничениями, является NP-полной
Проверка наличия КАКОГО-ЛИБО выбора опций, согласующихся с ограничениями, может быть выполнена довольно быстро, если вы ограничите каждую группу радиобоксов двумя вариантами (2SAT).

Так что в общем случае не рассчитывайте на полиномиальный алгоритм;существование таких алгоритмов подразумевало бы P= NP.

Что вы можете сделать:

Используйте алгоритм аппроксимации.Согласно статье в Википедии, на которую я ссылался, они часто вызывают у них подозрения.
Используйте SAT-решатель http://en.wikipedia.org/wiki/SAT_solver или связанный инструмент для подсчета голосов (к сожалению, я не знаю ни одного);люди создали множество эвристик, и эти программы, как правило, будут намного быстрее вашего самодельного решения.Существуют даже соревнования SAT, так что в настоящее время эта область очень быстро расширяется.
Проверьте, нужна ли вам такая общность.Возможно, ваша проблема имеет дополнительные допущения, и это изменит ее сложность.

Доказательства:

Легко показать, что подсчет количества решений равен # P, поэтому достаточно свести 2SAT к этому.Возьмем какой-нибудь пример 2SAT, например

(p1 или не p2) и (p2 или не p3)

Разрешить пользователю выбирать значения p1, p2, p3.Вы можете легко сформировать ограничения, которые сделают эту проблему разрешимой.Таким образом, количество возможных конфигураций = количество возможных назначений p1, p2, p3, что делает логическую формулу истинной.

Вы можете легко проверить, разрешен ли какой-то выбор опций или нет, так что это NP, так что достаточно свести 3SAT к этому.Возьмем какой-нибудь пример 3SAT, например

(p1 или p2 или не p3) и (p2 или не p1 или p4)

Дайте варианты:

группа p1 p1 истина p1 ложь

группа p2 p2false p2истина

группа p3 p3 ложь p3 истина

группа p4 p4false p4 истина

клаузе_1 группы c1a c1b c1c

клаузе_2 группы c2a c2b c2c

clause_1 будет контролировать первое предложение:(p1 или p2 или не p3).Точно, c1a будет проверяемым, если было выбрано p1true, c1b будет проверяемым, если было выбрано p2true, c1c будет проверяемым, если было выбрано p3false.Таким образом, ограничения заключаются в следующем:

p1 ложь <-> c1a

p2 ложь <-> c1b

p3 истина <-> c1c

То же самое с clause_2, константами являются

p2 ложь <-> c2a

p1 истина <-> c2b

p4false ( ложь ) <-> c2c

Если пользователь сможет выбрать все ответы (таким образом, количество конфигураций равно > 0), он докажет, что существует некоторая оценка переменных p1, ..., p4, которые делают экземпляр 3SAT истинным.И наоборот, если пользователь не сможет выбрать ответы, соответствующие предположениям (количество доступных конфигураций = 0), экземпляр 3SAT не будет удовлетворительным.Таким образом, знать, равен ли ответ > 0, означает знать, разрешим ли экземпляр 3SAT.

Конечно, это сокращение происходит за полиномиальное время.Конец доказательства.

Если вас не устраивает тот факт, что ответ может быть равен 0:это все еще NP-сложно, если вы игнорируете такие конфигураторы.(Вы бы добавили какой-нибудь "фиктивный" вариант ко всем группам и разрешили экспоненциально много вариантов, если бы "фиктивный" не был выбран.Это сложнее объяснить, поэтому я сделаю это по запросу.)

Это кратко упоминается в превосходном ответе sdcvvc выше, но может ли приближение Монте-Карло быть достаточно хорошим?Сгенерируйте N случайных конфигураций (где N выбрано таким образом, чтобы мощность вашего эксперимента была достаточно высокой:Я знаю недостаточно, чтобы помочь вам здесь), затем проверьте, сколько из них совместимы с вашими ограничениями.Экстраполируйте эту пропорцию на остальную часть вашего конфигурационного пространства.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow