我被要求编写一个程序来决定在产品配置的可能组合的数量。

的配置是非常简单的。即使它具有比这更多的功能，它可以被建模为几个无线电基（如UI控制），其中的n个选项之一已被选中。

的唯一一种可用于约束的是规则的说，如果选择了一个选项，不能选择其他选项。

所以，我想要做的是计算，可以配置不同的产品的数量，给定一组选项组和约束。

我犯了一个幼稚的办法来解决这个使用容斥原理 。但据我所看到的，基于该方法的任何算法应为O（2 ^ n）的，将无法正常工作运行。当然也有几种可能的优化，应该给体面的运行时间，但仍有很容易地构建最坏的情况。

这就是pretty的多我在哪里现在。有什么建议？

更新

我意识到我没有解释如何应用规则不够好。

有几组的选项。一个且只有一个选项必须每组中进行选择。可以有一个或多个选项中的一组。

只有一种类型的约束。如果方案A在一些组中选择，在其他组中，然后选择B不能被选中。可以有任意数量的限制，没有限制多少限制/规则应用于一个选项组或一个选项本身

因此​​，一个例子是：

第1组： X1 X2 X3 X4 X5

第2组： Y1 Y2 Y3

第3组： Z1 Z2 Z3 Z4

约束： X1＆LT; - > Y2 * X1＆LT; - > Z4 Y2＆LT; - > Z2

* 如果选择X1是第1组选中，然后选择Y2 2组无法选择。

使用容斥我会计算的组合的数量为

组合= C 无规则 - ç研究 [1] - ç研究 [2] - ç研究 [3] + C 研究 [1,2] + C 研究 [1,3] + C 研究 [2,3] - ç研究 [1,2,3]

其中，

C 无规则 = 5 * 3 * 4

C 研究 [A，B，C] =违反的组合数统治的a，b和c。

该方法不幸的是，需要2 ^ |规则|计算。

解决方案

好吧，我不能得到大约2 ^ N，但我可以减少样本集。要做到这一点，我们将计算组成约束。甲构成约束是约束，其中，如果选择在左边的所有选项，那么所有的在右侧的选项可以被选择，但是基于左侧选项没有其他约束可以适用。

我们需要计算所有可能构成约束从一组约束。虽然不是必须的，我们将修理通过交换左右手如果组右手比组左侧的较小的现有限制。这可能会减少一些构成约束，但更好的启发式是可能的交换。

我们还需要计算一个最小集合的，可任意选择为每个组选择。这个最小集合是通过从任何选项出现在一个由约束的左手可用选项的列表中删除计算机。

这是算法如下，但我没有证明它正确计算完工。我将证明，如果这样做，则它们可以被用于计算的可能组合的数量。

修正的约束，使得该组的左手的是小于或等于该组的右手。

撰写的约束：

排序的限制由左手

接着，每个约束：

倍，跟着它具有相同的左手说，把 X1＆LT所有约束的约束; - ＆GT; Y1 ， X1＆LT; - ＆GT; Y2 ... X1＆LT; - ＆GT; YN 到设置（X1）＆LT; - ＆GT;设置（Y1 ... YN） 如果撰写折叠约束每个已折叠的约束： x1为不是在已折叠的约束的右手 x1为不处于左手同一组中的任何元件的 添加折叠约束和所有的组合物的组折的限制

计算该最低设定，通过取所有选项和除去那些出现在固定约束的左手

现在，你可以计算的组合与下面的公式数量。让我们把CC一个沉稳的约束。然后，组合的数目是：

  C（集的最小值）+ CCC1 + ... + CCCN
 

其中：

C（最低设定）是可能的组合与最低组的数量。 CCCx是可能的组合，采取的最小集，替换任何群的量有与该选项上CCx中的左手的一个选项，然后除去上CCx中的右手任何选项的数目。

请注意，我们的前pression纯粹是添加剂。这意味着，对于前pression，得到预期的结果，以下两个条件必须为真：

没有两个术语它可以包含相同的组合。 在所有组合都必须遵守这些条款占了。 没有无效的组合，可以由任何条款产生。

有关的第一个证据，注意，没有两个不同的CC用相同的左手。如果两个分量载波具有相同的左手，但不同的右手，这将意味着存在是必须向CC的，或无效的约束之一被施加到其他的加成约束

由于没有两个CC上具有相同的左手，并且最小集不包含的定义任何CC内的左手，则任何两个的CC可以通过被选择为一个，但不是所述至少一个选项区分为其他。因此，任何两个的CC可以产生相同的组合。

有关的第二检验，请注意，CC集合的包含，根据定义，所有有效组合为左侧的选项。

假定有没有出现在任一的最小集合，也不是CC集合中的一个组合。如果该组合不包含任何左手选项，那么它必须是从最小的一组的组合，由定义。因此，它必须包含从左手选项。

由于CC集合的包含所有有效组合为左手，则有一个CC具有相同的左手选项。这个组合必须的，因此，不包括在该CC的任何组合的一个选项。但不包括在该CC内的唯一选项是那些出现在左手为其它的CC，和那些必须排除从它通过的约束。因为无论可能是这种情况，那么这样的组合可以不存在

对于第三个证据，让我们首先考虑的最小集合。的最小集不包含在任何组的左手任何选项。由于所有的约束条件是一体的左边，一个右边的选项之间，没有限制适用于最小集合。

现在让我们考虑CCS的。在CC有定义左手选项的有效组合。任何选项，是不符合的左手必须出现在右边，从右边的任何选项必须从最小集中删除。由于在最低设置在这里不兼容的自己开始不带任何选项，但可以在一个CC的任意组合没有满足的约束。

这结束的证明。

让我们看看这适用于从注释的例子：

  G1：X1，X2，X3
G2：Y1，Y2
G3：Z1，Z2，Z3

R1：X1＆LT;  - ＆GT; Y2
R2：X3＆LT;  - ＆GT; 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}＆LT;  - ＆GT; {Y2}  - 不在列表中，因为x1和X3的属于同一
                            组
R 1安培; R 5：{X1，Y2}＆其中 - →; {Y2}  - 不在列表中，因为R2的左手，Y2
                            出现在R1的右手
 

现在，让我们来看看有哪些选项可以在每一组：

 最小集：（X2），（），（Z1，Z2，Z3）
CC1：（1次），（），（Z1，Z2，Z3） - ，其中x1替换G1，G2从除去Y2
CC2：（×3），（），（Z1，Z2，Z3） - 与X3的替换G1，G2从除去Y2
CC3：（2次），（Y1），（Z2，Z3） - 与Y1替换G2，G3从除去Z1
CC4：（1次），（Y1），（Z2，Z3） - 取代的G1，其中x1，G2与Y1，除去y 2和Z1
CC5：（×3），（Y1），（Z2，Z3） - 替换G1组×3，G2与Y1，除去y 2和Z1
CC6：（2次），（Y2），（Z1） - 与Y2取代G2，除去Z2和Z3从G3
 

现在，让我们添加的东西了：

  C（最低设定）= 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（最小套装）+ CCC1 + CCC2 + CCC3 + CCC4 + CCC5 + CCC6
0 + 0 + 0 + 2 + 2 + 2 + 1 = 7
 

我会添加一个这里进一步思考。尽管只有6 5规则幼儿中心，超过预期，否则32而言要少得多，这些幼儿中心的计算与2 ^ N最糟糕的时候，因为对于每个规则，你必须比较，并将其结合起来，创造了迄今为止所有幼儿中心。你可能会认为他们为二进制数，其中一个位被设置如果规则被合并，而不是如果没有设置。

但是，不兼容的组合被丢弃向右走，让每一个新的规则进行组合，无需浪费时间上已被视为无效组合。此外，通过前手排序规则，在同一组中的连续规则可甚至没有测试对于不兼容，用正确的数据结构丢弃。

作为该特定示例示出，平均时间可以比2好得多^ N

替代算法和注意事项

还有的2-SAT和3 SAT一些谈话绕来绕去。看来，对我来说，这是一个2-SAT的问题，表现在每一个约束一个＆LT感; - ！一个|| B> B是实际的条款。因此，所有的约束一起可以只写为（X1 || Y2！）＆安培;＆安培;＆安培（×1 || Z4！）;及（Y2＆安培;！＆安培;！Z3）等。这意味着你可以解决它的在这你可以找到，如果有一个布尔值分配给每个选项会变成这个真实的的意义。还有就是这个由Aspall，赛普拉斯的Tarjan一个线性算法，用幻灯片presentation的这里。

但我们知道的约束是否可以解决与否的是不是有人问。什么是问是的号的方式的所有选项可以同时保持2-SAT问题真正进行设置。

现在，有有效的算法，用于计数的方法来满足2-SAT问题的数量。例如，本文 presents运行在1.2561的算法 N 。但是的即使是这样的不会帮助我们，因为我们需要知道的什么的解决方案是能够计算的满足该解决方案组合的数量。

根据维基百科，本文有一个算法，有效地枚举所有的解决方案，这是我们想要的。但是，如果算上已经是指数，所以会枚举。优于2 N ，也许，但仍指数。

如果我们做枚举所有解决方案，以2-SAT问题，的组合为每个组的数目由1乘以自由选择各组的量的，不会出现在任何约束选项，数给定无选项​​是由溶液选定

例如，服用previous集集团和约束。 2-SAT问题，包括相互排斥，是：

＆AMP（X1 || Y2！）;＆安培; （！×3 || Y2）及＆安培; ＆AMP（Y1 || Z1！）;＆安培; ＆AMP（Y2 || Z2！）;＆安培; ＆AMP（Y2 || Z3！）;＆安培;   （！×1 ||×3！）＆安培;＆安培; （！Y1 || Y2）及＆安培; （！Z1 || Z2）及＆安培; （！Z1 || Z3）及＆安培; （！Z2 ||！Z3）

的第一行是五规则。第二行是在同一个组中出现的约束规则的所有选项的互斥

的解决方案，这2-SAT问题是：

  X1 X3 Y1 Y2 Z1 Z2 Z3组合
真假真假假真假1
真假真假假假真1
真假真假假假假0
真假假假真假假0
真假假假假真假0
真假假假假假真0
真假假假假假假0
假真真假假真假1
假真真假假假真1
假真真假假假假0
假真假假真假假0
假真假假假真假0
假真假假假假真0
假假真真假假假虚假0
假假真假假真假1
假假真假假假真1
假假真假假假假0
假假假真真假假1
假假假真假假假0
假假假假真假假0
假假假假假真假0
假假假假假假真0
假假假假假假假0
 

在所述第一两个解决方案中，没有基团未经选择选项，因此，组合的数目是1。第三溶液没有选择用于组G3的选择，因此我们乘1由0。在该启动线与虚假，没有选择组G1选项，一个自由的选择：X2。所以我们乘1由1对他们来说，和由0，如果没有选择G2或G3选项（在这种情况下，可自由选择的数目为0）。

现在，有一个我怎么执行被选择的每个组中的一个选项，仍然算得上是2-SAT的问题。的问题，如所述的，具有两个隐式的限制：对于每个组，必须有一个，且只有一个选项进行选择。这两个约束可以写为：

＆NBSP;＆NBSP;＆NBSP;＆NBSP，X 1 || x 2 || x 3 （对于基团X与选项X 1 .. X 3 ） ＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆安培（X 1 || x 2 ！）;＆安培; ＆安培（X 1 || x 3 ！）;＆安培; （！x 2 ||！x 3 ）

后来的约束是2-SAT，前者为3-SAT对于任何不平凡的情况。碰巧的是，我不执行第一个约束，但伯爵就变成了0。计数算法应该是这样的：

对于约束较少的组合，由彼此相乘每组中的约束少的选项数。 对于约束完整组合，添加以下计数的结果： 对于每种溶液，乘各组约束少选项的数目，而不由相互评估为​​真的选项。

因此​​，对于每个基团，其中至少有一个约束少选项，该选择是隐式和匿名。对于每一个组，其中所有的选项是一些约束的一部分，如果没有选择，被选择则该组的计数变为0，并因此，组合该解决方案的数目变为0以及

这感觉就像作弊问题出来了一个有效> 2-SAT约束。毕竟，如果这是可能的，那么，3-SAT问题，可以只通过枚举解决方案，以它的2-SAT部分，然后丢弃每一件不满足它的3-SAT部分解决。唉，有一个根本区别，我可以识别：

不受这一问题的2-SAT部分解决了所有predicates不受任何进一步的约束。

由于在条款这个相当严格的约束条件，我们就可以通过枚举解决方案，以2-SAT明确约束解决这个问题。

如果有人想进一步追究，继续前进。我很满意我建议提高2 N 的解决方案。

I have been asked to program a routine to decide the number of possible combinations in a product configurator.

The configurator is really simple. Even though it has more features than this, it can be modeled as several "radio groups" (like the UI control) where one of n options has to be selected.

The only kind of constraints that can be used is rules that says if one option is selected another option can not be selected.

So what I want to do is to calculate the number of different products that can be configured, given a set of option groups and constraints.

I made a naive approach to solve this using the Inclusion-exclusion principle. However as far as I can see, any algorithm based on this method should run in O(2^n) which won't work. There are of course several possible optimizations that should give decent runtimes but there are still easily constructed worst case scenarios.

Thats pretty much where I am right now. Any suggestions?

Update

I realize I haven't explained how the rules applies well enough.

There are several groups with options. One and only one option must be selected in each group. There can be one or more of options in a group.

There is only one type of constraints. If option A in some group is selected, then option B in some other group can't be selected. There can be any number of constraints, there is no limit how many constraints/rules apply to a option group or an option itself.

So an example would be:

Group 1: x1 x2 x3 x4 x5

Group 2: y1 y2 y3

Group 3: z1 z2 z3 z4

Constraints: x1 <-> y2 * x1 <-> z4 y2 <-> z2

* If option x1 is selected in group1, then option y2 in group 2 can not be selected.

Using inclusion-exclusion I would calculate the number of combinations as

Combinations = Cno rules - Cr[1] - Cr[2] - Cr[3] + Cr[1,2] + Cr[1,3] + Cr[2,3] - Cr[1,2,3]

Where

Cno rules = 5 * 3 * 4

Cr[a,b,c] = Number of combinations that violates rule a, b and c.

The method unfortunately requires 2^|rules| calculations.

解决方案

Ok, I can't get around 2 ^ N, but I can reduce the sample set. To do this, we'll compute "Composed Constraints". A Composed Constraint is a constraint where, if the all options on the left side is selected, then none of the options on the right side can be selected, but no other constraint based on the left side options may apply.

We need to compute a set of all possible Composed Constraints from a set of constraints. While not necessary, we'll "fix" the existing constraints by swapping left and right hands if the group of the right hand is smaller than the group of the left. This may reduce some composed constraints, though better heuristics are possible for swapping.

We also need to compute a "minimum set" of options that can be arbitrarily chosen for each group. This minimum set is computed by removing from the list of available options any options appearing on the left hand of a composed constraint.

An algorithm follows, but I'm not proving it computes CCs correctly. I will prove that, if it does, then they can be used to compute the number of possible combinations.

Fix the constraints so that the group of the left hand is less than, or equal to the group of the right hand.

Compose the constraints:

Sort constraints by left hand

Sequentially, for each constraint:

Fold the constrain with all constraints that follow it with the same left hand, turning x1 <-> y1, x1 <-> y2 ... x1 <-> yN into Set(x1) <-> Set(y1 ... yN) Compose the folded constraint with each already folded constraint, if: x1 is not in the right hand of the already folded constraint x1 is not in the same group of any element in the left hand Add the folded constraint and all it's compositions to the set of folded constraints

Compute the Minimum Set, by taking all options and removing the ones appearing in the left hand of the fixed constraints.

Now you can compute the number of combinations with the formula below. Let's call CC a composed constraint. Then the number of combinations is:

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

Where:

C(Minimum Set) is the number of combinations possible with the minimum set. CCCx is the number of combinations possible by taking the minimum set, replacing any groups for which there's an option on the left hand of CCx with that option, and then removing any options on the right hand of CCx.

Note that the expression is purely additive. This means that, for that expression to yield the expected result, the following two conditions must be true:

No two terms of it may contain the same combination. All combinations must be accounted for by these terms. No invalid combinations may be yielded by any term.

For the first proof, note that there are no two distinct CCs with the same left hand. If two CCs had the same left hand but different right hands, that would mean there was an addition constraint that must apply to one of the CCs, or an invalid constraint being applied to the other.

Since there are no two CCs with the same left hand, and the minimum set does not contain the left hand of any CC by definition, then any two CC can be distinguished by at least one option which is selected for one but not for the other. Therefore, no two CCs may yield the same combination.

For the second proof, note that the set of CCs contains, by definition, all valid combinations for options on the left hand.

Assume that there is one combination that does not appear in either the minimum set nor the set of CCs. If this combination does not contain any left-hand option, then it must be a combination from the minimum set, by definition. Therefore, it must contain options from the left hand.

Since the set of CCs contains all valid combinations for the left hand, then there is one CC with the same left-hand options. This combination must have, therefore, an option that is not included in any combination for that CC. But the only options not included in that CC are the ones appearing in the left hand for other CCs, and the ones that must be excluded from it by constraints. Since neither may be the case, then this combination cannot exist.

For the third proof, let's first consider the minimum set. The minimum set does not contain any option in the left hand of any group. Since all constraints are between one left and one right hand option, no constraint applies to the minimum set.

Now let's consider the CCs. A CC has a valid combination of left hand options by definition. Any option that is incompatible with that left hand must appear in the right hand, and any option from that right hand must be removed from the minimum set. Since no options on the minimum set where incompatible between themselves to begin with, there can be no unsatisfied constraint in any combination on a CC.

And that ends the proof.

Let's see how this applies with an example from the comments:

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}

Let's ponder briefly on composed groups not in the list:

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

Now, let's see what options are possible in each set:

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

Now, let's add things up:

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

I'll add one further thought here. Even though there are only 6 CCCs for 5 rules, much less than the 32 terms expected otherwise, these CCCs are computed with 2^N worst time, since, for each rule, you must compare and combine it to all CCCs created so far. You may think of them as binary numbers, where a bit is set if the rule is being combined, and not set if not.

However, incompatible combinations are discard right away, so that for each new rule being combined, no time is lost on combinations already deemed invalid. Also, by sorting the rules before-hand, successive rules in the same group may be discarded without even testing for incompatibility, with the right data structures.

As this particular example shows, the average time can be much better than 2^N.

Alternative Algorithms and Considerations

There's some talk of 2-SAT and 3-SAT going around. It seems, to me, that this is a 2-SAT problem, in the sense that every constrain a <-> b is actually a clause "!a || !b". So all constrains together can just be written as "(!x1 || !y2) && (!x1 || !z4) && (!y2 && !z3)", etc. That means you can "solve" it in the sense that you can find out if there is a boolean assignment to each option that will turn this true. There is a linear algorithm for this by Aspall, Plass and Tarjan, with a slide presentation here.

But knowing whether the constrains can be solved or not is not what was asked. What was asked is the number of ways all options can be set while keeping the 2-SAT problem true.

Now, there are efficient algorithms for counting the number of of ways to satisfy a 2-SAT problem. For instance, this paper presents an algorithm that runs in 1.2561n. But even this won't help us, as we need to know what the solutions are to be able to compute the number of combinations that satisfy that solution.

According to Wikipedia, this paper has an algorithm which efficiently enumerate all solutions, which is what we want. But if counting is already exponential, so will be enumerating. Better than 2n, perhaps, but still exponential.

If we do enumerate all solutions to the 2-SAT problem, the number of combinations for each group is given by 1 multiplied by the number of free options, options that do not appear in any constraint, of each group for which no option was selected by the solution.

For example, taking the previous set of groups and constraints. The 2-SAT problem, including mutual exclusion, is:

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

The first line are the five rules. The second line is the mutual exclusion of all options in the same group that appear in the constraint rules.

The solutions to this 2-SAT problems are:

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

In the first two solutions, there are no groups without a selected option, so the number of combinations is 1. The third solution has no option selected for the group G3, so we multiply 1 by 0. In the lines that start with "false false", there are no option selected for group G1, and one free option: x2. So we multiply 1 by 1 for them, and by 0 if there are no option selected for G2 or G3 (in which case the number of free options is 0).

Now, there is the question of how do I enforce one option being chosen in each group and still claim to be 2-SAT. The problem, as stated, has two implicit constraints: for each group, there must be one, and only one, option selected. These two constrains can be written as:

x1 || x2 || x3 (for group x with options x1 .. x3) (!x1 || !x2) && (!x1 || !x3) && (!x2 || !x3)

The later constrain being 2-SAT, the former being 3-SAT for any non-trivial case. As it happens, I do not enforce the first constraint, but the count then becomes 0. The counting algorithm should go like this:

For the constraint-less combinations, multiply the number of constraint-less options in each group by each other. For the constraint-full combinations, add the result of the following counts: For each solution, multiply the number of constraint-less options in each group without an option evaluated to "true" by each other.

So, for every group in which there is at least one constraint-less option, the selection is implicit and anonymous. For every group in which all options are part of some constraint, if no option was selected then the count for that group becomes 0, and, therefore, the number of combinations for that solution becomes 0 as well.

This feels like cheating the problem out of a valid > 2-SAT constraint. After all, if this was possible, then the 3-SAT problem could be solved just by enumerating the solutions to the 2-SAT part of it, and then discarding every one which does not satisfy the 3-SAT part of it. Alas, there is one fundamental difference I can identify:

All predicates not solved by the 2-SAT part of the problem are free from any further constraints.

Given this rather restrictive constraint on the clauses, we can solve this problem by enumerating solutions to the 2-SAT explicit constraints.

If anyone wants to pursue this further, go ahead. I'm satisfied with the improvement on the 2n solution I suggested.