在配置组合数(Number of combinations in configurator)

2019-07-30 11:52发布

站内文章 / 前端开发

44 0

疯言疯语

女 | 书童

私信

我一直在问一个例行程序，以决定在产品配置的可能组合的数量。

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

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

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

我做了一个幼稚的方法来解决这个使用容斥原理。但是据我所看到的，基于该方法的任何算法应该在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

*如果选项X 1为组1中的选择，则在组2的选项Y2不能被选择。

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

组合= 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 ^ |规则| 计算。

Answer 1:

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

我们需要计算所有可能构成约束从一组约束。虽然没有必要，我们将“修复”通过交换左右手，如果该组的右手比组左侧的小存在的制约因素。这可以减少一些组成约束，但更好的启发式可能用于交换。

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

算法如下，但我没有证明它正确计算的CC。我将证明，如果这样做，那么他们可以被用来计算的可能组合的数量。

固定的约束，使得该组的左手的是小于或等于该组的右手。
撰写的制约：
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右手任何选项可能的组合的数量。

注意，表达式是纯粹的添加剂。这意味着，对于表达，以产生期望的结果，以下两个条件必须为真：

它没有两个条款可能包含相同的组合。
所有组合都必须由这些术语来解释。
没有无效的组合可以由任何条款来得到。

对于第一个证据，指出没有两个不同的CC具有相同的左手。如果两个CC有相同的左手，但不同的右手，这将意味着有必须适用于CC时，或无效的约束之一被应用到其他的附加约束。

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

对于第二个证据，指出该组CC包含，通过定义，在左手上选择的所有有效组合。

假设有没有出现无论是在最低限度，也不该组CC的一个组合。如果这种组合不包含任何左手选项，那么它必须从最小集合组合，顾名思义。因此，它必须包含从左手选项。

由于该组CC包含了左手的所有有效组合，然后有一个CC具有相同左侧的选项。这种组合必须的，因此，不包括在该CC的任意组合的选项。但不包括在CC的唯一选项是出现在左手其他CC的那些，并且必须从它的限制被排除在外的。因为无论可能是这种情况，那么这种组合可以不存在。

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

现在，让我们考虑的CC。一个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

在这里我要补充一个进一步的思考。尽管只有6个幼儿中心5条规则，高于预期，否则32项少得多，这些幼儿中心的计算与2 ^ N最坏的时候，因为对于每个规则，你必须比较，并结合创建至今所有幼儿中心。你可以认为他们是二进制数，其中如果规则被结合的位设置，而不是如果没有设置。

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

由于这个特定的例子示出的平均时间可以大于2 ^ N好得多。

另类算法和注意事项

有2-SAT和3-SAT的一些谈话绕来绕去。看来，对我来说，这是一个2-SAT问题，在这个意义上，每一个约束< - > b实际是一个子句“一|| b！”。因此，所有的约束在一起正好可以写成“（！X1 ||！Y2）&&（！X1 ||！Z4）&&（！Y2 &&！Z3）”等，这意味着你可以在这个意义上 “解决”它你可以找出是否有一个布尔值分配到会变成这个真实的每个选项 。有这种线性算法通过Aspall，赛普拉斯的Tarjan，用幻灯片演示在这里。

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

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

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

如果我们列举的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的选择，因此我们通过0乘以1中以“假启动线假”，没有选择组G1选项，一个自由选择：X2。所以，我们乘1 1对他们来说，和0，如果没有选择G2或G3（在这种情况下自由选择数为0）选项。

现在，有的我怎样执行被选择的每个组中的一个选项，并仍然声称是2-SAT的问题。该问题，如所述的，具有两个隐式的约束条件：对于每个组，必须有一个且只有一个，选择的选项。这两个约束可以写成：

X ₁ || _×2 || _×3（用于选择X ₁基团X _..×3）
（！X ₁ _{||！×2）&&（！X} ₁ _{_{||！×3）&&（！×2}} _||！×3）

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

对于约束较少的组合，乘以由每个其它各组约束的更少的选项数。
对于约束的全组合，添加以下计数的结果：
- 对于每种溶液，乘的每个组中的约束少选项的数目而不会被彼此评估为“真”的选项。

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

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

没有问题的2-SAT部分解决了所有谓词是任何进一步的限制自由。

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

如果有人想进一步追究，勇往直前。我很满意在2 ^n个解决办法，我建议的改进。

Answer 2:

如果你有N选项组，每组Xi选项（ 0<=i<N则

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

给你你想要的答案。换言之，乘法每个组的选项的大小。

Answer 3:

如果你有n与参数Ci每个参数和可能的值m的限制，一个上限configuartions的数量为下面的（忽略约束）。

N0 = C1 * C2 * ... * Cn

形式的单个约束ci == x => cj != y不允许下列数目的配置。

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

因此配置的数目是通过从上限忽略约束减去不允许configuartions获得。

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

UPDATE

我想是因为它没有考虑约束的依赖，这还不是完全地正确。

Answer 4:

~~这里没有捷径的一般情况。~~ 它并不像你想象的那样糟糕。请参阅“反思”的下方。

为2 ^ N真的那么糟糕吗？我们有多少排除规则都在谈论这里？你真的只需要为每个配置做一次，除非规则的集合/选项是不断变化的飞行，并要求重新计算动态。如果有真正的规则数量庞大，那么我将不寻求确切的结果 - 只考虑k阶交叉，并说“组合的数量至少为/最...”。有可能是其他筛方法，可以让你很快就得出了答案范围。

同时请记住：如果你只考虑排除你的实际需要，然后2 ^ n是只是一个上限，您的实际计算的数量可能是任何实际场景显著少。即，如果C [1,2]是零，则这样是C [1,2，...]。如果他们共享任何选项，每个约束，“块体”约束的套在一起：考虑这一点。很明显，你的实际运行时间将是由最大的“丛”（其中，是的，可能是正为大）的大小来定义。

反思：C [X，Y]将是在大多数情况下为零。约束只能与涉及不同组的其他约束重叠。换句话说，（X1 < - > Y1） - 或（Y1 < - > Z2）或东西，而不是（X1 < - > Y2）只能与（<> Z1 X1）重叠。类似地，一组约束只能与一个新的组重叠：的（X1 < - > y1）上结合（Y1 < - > Z2）与没有相互作用（X3 < - > Z2）（X基团是已经固定在X1）。你只需要考虑包含/排除其中每个你添加到组合规则增加了先前不变组的组合。所以，你实际上是O（2 ^G），其中G是组（也可能是基于组的大小不同的约束）的数量。更容易管理！

Answer 5:

编辑

这种算法不正确。我已经提出了在另一篇文章这仍然是2 ^ N在最坏的情况下的替代答案，但可能会以其他方式提供更好的结果。

在choosen因为Y2是设定X1排除的一部分，以及两个第一约束是基于X1的例子这一个工程。不过，我看现在需要做什么。它仍然接近2 ^ N，但也有优化，这可能会导致显著的收益。

为了解决这个问题的算法，所构成的规则的形式必须是集（牛）的< - >组（OY）。要编写他们，每个左手牛约束您撰写，也使的它的其他成分，每个你已经组成规则， 如果牛是不是由规则的右手边的一部分，也不是组是相同组的左手侧 。

为完全独立的约束，这是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

如果我的算法是正确的，这似乎是多项式。同样，现在我不能想清楚不够，我需要考虑在套操作的大O。

下面是一个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)
}

Answer 6:

这可能不是一个直接有用的答案，可以随意忽略它。不过，我目前的工作没有自己的类似系统; 并坦言比简单的例子其他我不知道它是有益的尝试，计算有效组合的数量。举个例子，我是做什么工作的模型有（例如）18000个候选项目遍及80多个选择，一些单选择/一些多选。除了最小的车型，有在明知的数量，你就根本不会把它写成一个完整的真值表没有好处 ; 你漂亮，很多被迫运行规则（即删除任何不再有效，自动选择什么合适，并确认是否有规则被打破）点播。这不一定是一个问题; 我当前的代码处理该模型（作为web服务）在〜450ms，以及最的，它实际上是用于输入/输出所花费的时间的处理的XML。如果输入/输出不是XML，我认为这将是150毫秒〜，这是很酷。

我很想说服我的雇主开源引擎; 这是另一天战斗，虽然。

Answer 7:

会不会只是为x ^ n，其中n是选项和X的数量是每个选项选择的数量？

Answer 8:

我觉得扎克是在正确的方向思考。看你的表现了组合的数量，你看到二阶项铬[I，J]比C [k]的条款小得多。想象一个立方体，其中每个轴是一组选项。在立方体的每一个点代表的选项的特殊组合。一阶C [k]的校正不包括的线的立方体的两个表面之间的选择。二阶修正C [I，J]仅当两个这样的线在所述立方体的一个点（选项组合）在空间满足发生。所以不管你有群体的数量，高阶修正总是越来越小。如果你坚持

组合= C（无规则） - 铬[1] - 铬[2] - 的Cr [3]

你结束了一个下界组合的数量。现在，你知道你的第一个订单修正的规模，并考虑与上面的立方体观察，你甚至可以估算二阶校正的量级。这将取决于组的数量。那么你的算法可以决定是否要继续高阶或停止。

Answer 9:

评论对丹尼尔的帖子：

你的算法看起来不错，但我无法说服自己这果然奏效，所以我安装Scala和做一些测试。 Unfortunaly我没有得到正确的结果。

例如，考虑这种情况下：

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。

我检查在筛法的计算，他们似乎是正确的。也许有可能解决您的算法？我真的不能把我的手指上的什么是错的。

Answer 10:

你的问题是相当不可行的。

计数解决方案的数量为＃P-完整的，即使你每一组选项框的限制为两个选项
检查是否有与约束的一致选择任何选择是NP完全问题
检查是否有与约束条件选项中的任何选择可以做得相当快，如果你限制每个组选项框的两个选项（2SAT）

所以一般不会在一个多项式算法计算; 这种算法的存在意味着P = NP。

你可以做什么：

使用一个近似算法。根据维基百科的文章我联系，他们往往suspectible他们。
使用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组 p1true p1false

P2组 p2false p2true

P3组 p3false p3true

组P4 p4false p4true

组clause_1 C1A C1B C1C

组clause_2 C2A C2C C2B

clause_1将控制第一子句：（P1或P2或不P3）。准确地说，C1A将成为可检查的，如果选择p1true，C1B将成为可检查的，如果选择p2true，如果p3false选择C1C将是可检查的。因此，约束是：

p1false < - > C1A

p2false < - > C1B

p3true < - > C1C

同样的，clause_2，constaints是

p2false < - > C2A

p1true < - > C2B

p4false < - > C2C

如果用户将可以选择所有的答案（这样配置的数量> 0），他会证明有变量P1，......，P4，使该3SAT实例真实一些的估值。反之，如果用户将不能够选择的答案用的假设（可用配置= 0的个数）一致时，3SAT实例不会被satisfable。因此，了解如果答案是> 0，表示知道，如果3SAT实例是可解的。

当然，这种减少是多项式时间。证明结束。

如果你不满意的事实，答案可能是0：如果你忽略这样的配置器它仍然是NP难。（你会添加一些“假”选项，所有的组，并允许成倍很多选择，如果“假”没有被选中，这是比较复杂的解释，所以我会做到这一点的要求。）