algorithm - 配置器中的组合数

Question

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

配置器非常简单。即使它具有更多功能，也可以将其建模为几个“无线电组”（如UI控件），其中必须选择n个选项之一。

可以使用的唯一约束类型是规则，该规则指出如果选择了一个选项，则不能选择另一个选项。

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

我天真地使用Inclusion-exclusion principle解决了这个问题。但是据我所知，任何基于此方法的算法都应在O（2 ^ n）中运行，这将无法正常工作。当然，有几种可能的优化应该可以提供不错的运行时，但是仍然很容易构建最坏的情况。

那就是我现在所在的位置。有什么建议？

更新资料

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

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

只有一种约束。如果选择某组中的选项A，则无法选择其他组中的选项B。可以有任意数量的约束，对选项组或选项本身有多少个约束/规则没有限制。

因此，一个例子是：

第一组：
x1 x2 x3 x4 x5

第2组：
y1 y2 y3

第3组：
z1 z2 z3 z4

限制条件：
x1 <-> y2 *
x1 <-> z4
y2 <-> z2

*如果在组1中选择了选项x1，则不能在组2中选择选项y2。

使用包含-排除，我将计算组合的数量为

组合= Cno规则-Cr [1]-Cr [2]-Cr [3] + Cr [1,2] + Cr [1,3] + Cr [2,3]-Cr [1,2,3]

哪里

Cno规则= 5 * 3 * 4

Cr [a，b，c] =违反规则a，b和c的组合数。

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

Answer 1

好的，我不能达到2 ^ N，但是我可以减少样本集。为此，我们将计算“组合约束”。组合约束是一种约束，其中，如果选择了左侧的所有选项，则不能选择右侧的所有选项，但是基于左侧选项的其他约束均不适用。

我们需要从一组约束中计算出一组所有可能的组合约束。虽然不是必需的，但如果右手的组小于左手的组，我们将通过交换左手和右手来“修复”现有约束。尽管可以使用更好的启发式方法，但是这可以减少一些组合约束。

我们还需要计算可以为每个组任意选择的选项“最小集”。通过从可用选项列表中删除出现在组合约束左侧的所有选项来计算此最小集合。

遵循一种算法，但是我不能证明它可以正确计算CC。我将证明，如果可以，那么它们可以用于计算可能组合的数量。


修正约束，使左手的组小于或等于右手的组。
组成约束：


用左手排序约束
对于每个约束，依次：


用相同的左手折叠约束并遵循所有约束，将x1 <-> y1，x1 <-> y2 ... x1 <-> yN变成Set(x1) <-> Set(y1 ... yN)
如果满足以下条件，则将折叠约束与每个已经折叠的约束组成：


x1不在已折叠约束的右边
x1与左手元素不在同一组

将折叠约束及其所有组成部分添加到折叠约束集合中


通过选择所有选项并删除固定约束左侧出现的选项，计算最小集。


现在，您可以使用以下公式计算组合数量。我们称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具有左手选项的有效组合。与该左手不兼容的任何选项都必须出现在右手中，并且该右手中的任何选项都必须从最小集合中删除。由于最小集上没有选项彼此之间不兼容，因此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个CCC，比其他32个术语要少得多，但这些CCC的计算最差时间为2 ^ N，因为对于每条规则，您都必须将其与迄今为止创建的所有CCC进行比较和组合。您可能会认为它们是二进制数，如果将规则组合在一起，则将其设置为一个二进制数，否则将不被设置。

但是，不兼容的组合会立即被丢弃，因此对于每个组合的新规则，已经被视为无效的组合都不会浪费时间。同样，通过事先对规则进行排序，可以使用正确的数据结构丢弃同一组中的连续规则，甚至无需测试不兼容性。

如该特定示例所示，平均时间可能比2 ^ N好得多。

替代算法和注意事项

有一些关于2-SAT和3-SAT的讨论。在我看来，这是一个2-SAT问题，从某种意义上说，每个约束a <-> b实际上都是子句“！a ||！b”。因此，所有约束都可以写成“（！x1 ||！y2）&&（！x1 ||！z4）&&（！y2 &&！z3）”，依此类推。这意味着您可以在某种意义上“解决”它您可以找出是否对每个选项都进行了布尔赋值，以使此结果变为true。 Aspall，Plass和Tarjan对此有一个线性算法，并带有幻灯片演示 here。

但是，并不是要问约束是否可以解决。所要求的是在保持2-SAT问题为真的情况下可以设置所有选项的方式数量。

现在，有一些有效的算法可以计算满足2-SAT问题的方式数量。例如， this paper提出了一种在1.2561n中运行的算法。但这甚至无济于事，因为我们需要知道解决方案是什么，以便能够计算出满足该解决方案的组合数量。

根据Wikipedia所述， this paper具有一种可以有效枚举所有解决方案的算法，这正是我们想要的。但是如果计数已经是指数的，那么将被枚举。也许比2n好，但仍然是指数级的。

如果我们确实列举了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选择任何选项，并且没有一个可用选项：x2。因此，我们将它们乘以1，如果没有为G2或G3选择任何选项（在这种情况下，可用选项的数量为0），则乘以0。

现在，存在一个问题，即我如何强制在每个组中选择一个选项，并且仍然声称自己是2-SAT。如上所述，该问题具有两个隐式约束：对于每个组，必须选择一个，并且只能选择一个选项。这两个约束可以写成：

x1 || x2 || x3（对于带有选项x1 .. x3的组x）
（！x1 ||！x2）&&（！x1 ||！x3）&&（！x2 ||！x3）

对于任何非平凡的情况，后一种约束是2-SAT，前一种约束是3-SAT。碰巧的是，我没有强制执行第一个约束，但是计数变为0。计数算法应如下所示：


对于无约束组合，将每个组中无约束选项的数量彼此相乘。
对于完全约束组合，请添加以下计数的结果：


对于每个解决方案，将每个组中无约束选项的数量相乘，而彼此之间没有选项被评估为“ true”。



因此，对于每个至少有一个无约束选项的组，选择是隐式且匿名的。对于所有选项都属于某个约束的每个组，如果未选择任何选项，则该组的计数将变为0，因此该解决方案的组合数也将变为0。

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


问题的2-SAT部分未解决的所有谓词都不受任何进一步的约束。


给定这些对子句的限制性约束，我们可以通过枚举2-SAT显式约束的解决方案来解决此问题。

如果有人想进一步追求这一点，请继续。我对我建议的2n解决方案的改进感到满意。