数量组合在配置

https://stackoverflow.com/questions/1154565

18-09-2019
|

题

我已要求程序的一个例行决定可能的组合数量的产品配置。

该配置是非常简单的。即使它具有更多功能于这一点，它可以模仿几个"无线电组"(喜欢的UI控制)，其中一个n的选择具有可行选择。

唯一的一种制约因素可以使用的规则说，如果一个选择是选择另一个选择不能选择。

所以我要做的是计算数量的不同产品，可以构成，给予一组选项组和制约因素。

我做了一个幼稚的方法来解决这个用的列入排除原则.但是我可以看到，任何算法，根据这种方法应该在O(2^n)这不会的工作。当然，还有几个可能的优化，应该得到体面运行，但仍有很容易构成的最坏的情况。

这就是很多我在哪里，现在。任何建议？

更新

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

有几个团体的选择。一个和唯一一个选项的选择必须在每个组。可以有一个或更多的选择在一个组。

只有一种类型的约束。如果选择一个在一些集团选择然后选择B在一些其他组不能进行选择。可能有任何数量的约束条件，是没有限制的如何许多制约因素/规则适用于一个选项组或一项选择本身。

这样的一个例子将是：

第1组：
x1x2x3 4x5

第2组：
y1y2y3

第3组：
z1y2z3z4

制约因素：
x1 <->y2*
x1 <->z4
y2 <->y2

* 如果选择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|计算。

解决方案

Ok，我不能获得约2^正，但我可以减少对样品设置的。要做到这一点，我们将计算"组成的约束"。一个由约束是一个制约这里，如果的所有选项的左侧被选中，那么没有任何选择在右边可选择，但是没有其他约束基于左侧的选择可能适用。

我们需要一个计算所有可能构成限制从设置的限制。虽然没有必要，我们将"修正"现有的约束，通过交换左手和右手如果组的右手，是比较小组的离开。这可能降低一些成约束，虽然更好的启发是可能的交换。

我们还需要计算出一个"最小"的选项，可以任意选择对各个小组。该小组计算出的通过删除从清单中可供选择的任何选项出现在左手的一个组成约束。

一种算法，但是我没有证明它计算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是组合的数量可能采取的最小的组，取代任何群体因为其中有一个选项的左手的公司与该选项，然后删除任何选择权方面的公司.

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

没有两个方面，它可能包含相同的组合。
所有组合中必须考虑通过这些条款。
没有无效组合可以产生通过任何术语。

第一证据，请注意，没有两个不同的CCs有相同的左手。如果两个CCs有同样的左手但是，不同正确的人手中，这将意味着有一个另外的约束，必须适用于一个CCs，或者无效的约束，正应用到其他。

由于没有两个CCs有相同的左手和最小的一组不含有左手的任何CC通过的定义，那么任何两个CC可以通过至少一个选项，而是选择之一而不是其他。因此，没有两个CCs可能产生相同的结合。

第二证明，注意设置的CCs包含，通过定义，所有有效的组合上的选项的左手。

假设有一个组合就不会出现在任何一本最低，也没有设置的CCs。如果这个组合并不包含任何左手的选择，那么它必须是一种组合从最小的一组，通过的定义。因此，它必须包含选项从左手。

由于设置的CCs包含所有有效的组合，左手,然后有一个c-c有同样的左手的选择。这种组合必须具备的，因此，一个选项，不包括在任何组合，CC。但是唯一的选项不包括在CC是那些出现在左手用于其他CCs，以及那些必须被排除在它的约束。由于既不可能是这种情况，则这种组合不能存在。

第三证明，我们首先考虑最小的设置。该小组并不包含任何选择在左手的任何组。由于所有的约束之间，一个左一个右手的选择，没有约束适用于最小的设定。

现在，让我们考虑的CCs。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-坐了绕来绕去。它似乎对我来说，这是一个2-坐问题，在这个意义上，每一个限制 <->b实际上是一个条款"!a||!b"。因此，所有制约了一起可以写为"(!x1||!y2)&&(!x1||!z4)&&(!y2&&!z3)"，等等。这意味着你可以"解决"它 在这个意义上，可以找出如果有一个布尔的分配到每个选项，将把这个真的.有一个线性的算法为此通过Aspall,难忘记和陶尔扬与一个幻灯片演示在这里，.

但我们知道是否限制了可以解决或者不 不是什么要求.什么要求是的数量方面的所有选择可以是设置同时保持2-坐问题，真的。

现在，有高效率的算法计数的方法来满足2-星期六的问题。例如，这纸提出了一种算法，行在1.2561ⁿ.但 即使是这个 不会帮助我们，因为我们需要知道 什么样的 该解决方案能够计算数量的组合，以满足这一解决办法。

根据Wikipedia，这纸有一种算法，这有效地列举所有解决方案，这是我们想要什么。但是，如果计数已经是指数，因此将列举了.比2ⁿ, 也许，但仍指数。

如果我们一一列举所有的解决方案2-坐问题的数量的组合，每个组由1的数量乘以自由选择，选择，不会出现在任何约束，每个小组对于没有选择的解决方案。

例如，如果以前设置的团体和制约因素。2-坐问题，包括相互排斥，是:

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

第一线是五个规则。第二条线是相互排斥的所有选择同一集团中出现的约束的规则。

解决这2-星期六的问题是：

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.在该行以"虚假"，没有选择为基G1，和一个免费的选项：x2。因此，我们乘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。该计算法应该是这样的：

对于约束的小组合、数乘以约束少选项，在每个组由每一方。
对于约束的全组合，添加以下的结果：
- 对于每个方案，数乘以约束少选择中的每个集团没有一个选项评估"真正的"通过。

因此，对于每个组在其中至少有一个限制条件更少的选择，选择是隐性的和匿名的。对于每一个集团在其所有选项都是部分一些约束，如果没有选择，然后计数用于该组变为0，因此，数组合对这一解决办法变为0。

这感觉就像在作弊问题的一个有效>2-星期六的约束。毕竟，如果这是可能的，那么第3-坐问题可以解决刚刚通过列举的解决办法2-SAT的一部分，它,然后丢弃的每一个，它不满足3-坐一部分。可惜的是，有一个根本的区别，我可以确定：

所谓没有解决由2-坐一部分的问题都是免费的任何进一步的限制。

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

如果任何人想要追求这进一步，继续前进。我很满意的改善2ⁿ 解决我的建议。

其他提示

如果您已N选项组，每组Xi选项（0<=i<N）然后

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

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

如果你有每个参数和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

<强>更新

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

~~这里没有捷径的一般情况。~~这并不像你想象的那样糟糕。看看 “重新思考” 的下方。

时的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基团已经被固定在1次）。你只需要考虑包含/排除其中每个你添加到组合规则增加了先前不变组的组合。所以你实际上是O（2 ），其中G是基团（以及或许根据该组的大小不同的约束）的数目。更易于管理！

编辑

这个算法是不正确的。我已经提出了一个备用答案在另一篇文章中，这仍然是2^正在更糟的情况，但可能会得到更好的结果。

这一工作的示例中选择，因为y2是部分排除设定的x1，两个第一限制是基于x1。仍然，我现在看看有什么需要做的事情。它仍然接近2^正，但有的优化，这可能会导致重大的收益。

要解决这个算法，组成规则的必须的形式设置(牛) <->组(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的操纵集。

这里是卡拉实施的：

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多个选择，一些单选择/一些多选。除了最小的车型，没有的好处的在明知的数量，你就根本不会把它写成一个完整的真值表;你是漂亮，多少强制运行规则（即删除任何不再有效，自动选择什么合适，并确认是否有规则被打破）点播。这不一定是一个问题;我当前的代码处理该模型（作为web服务）在〜450ms，以及最的，它实际上是用于输入/输出所花费的时间的处理的XML。如果输入/输出不是XML，我认为这将是150毫秒〜，这是凉爽。

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

不会它只是为x ^ n，其中n是选项并且x的数量的每选项选择的数目？

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

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

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

注释来丹尼尔的帖子：

您算法看起来不错，但我无法说服自己这果然奏效，所以我安装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***

但是使用此代码在阶：

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-完整的，甚至如果你限制了每个组radioboxes到两个选择

检查是否有任何选择的选项一致的约束是NP-完成

检查是否有任何选择的选项一致的约束，可以相当快的，如果限制每个集团的radioboxes两个选项(2SAT)

因此，在一般情况下不指望在一个多项式的算法；存在着这样的算法将意味着P=NP。

你可以做什么：

用一种近似的算法。根据维基百科的文章我相联系，他们往往suspectible给他们。

使用坐了解 http://en.wikipedia.org/wiki/SAT_solver 或一个有关工具，用于计数(不幸的是，我不知道任何);人们已经创造了许多启发式和程序将在大得多的速度比你的自制的解决方案。甚至还有周六的比赛，因此这个领域的是目前正在扩大速度非常快。

如果你需要这样的普遍性。也许你的问题具有额外的假设，这将改变其复杂性。

证据:

计数的解决方案是很容易显示可#P，因此它的不足以降低2SAT到这一点。采取一些2SAT实例，就像

(p1或不p2)和(p2或不p3)

允许用户选择值的p1，p2,p3。你可以很容易地形成的约束，这将迫使这是可以解决的。如此数量的可能配置=数目可能分配的p1，p2,p3使得布尔公式正确的。

你可以轻易地检查，如果一些选项的选择是允许或没有，这是NP，使它足以减少3周六到这一点。采取一些3周六的实例，喜欢

(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 c2b c2c

clause_1将控制的第一个条款：(p1或p2或不p3)。确切地说，c1a将是可选的，如果p1true是选择，c1b将是可选的，如果p2true是选择，c1c将是可选的，如果p3false。这样的限制是：

p1false <->c1a

p2false <->c1b

p3true <->c1c

同clause_2,constaints是

p2false <->c2a

p1true <->c2b

p4false <->c2c

如果用户将能够选择的所有答复(所配置数是>0)，他会证明，那里是一些评估的变量p1、...、p4，使3周六的实例正确的。反之，如果用户不能选择回答一致的假设(数量的可用配置=0)，3周六的实例不会satisfable.所以知道如果答案是>0意味着知道如果3周六的实例是可以解决的。

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

如果你不满意的事实的回答可能是0:它仍然是NP-很难，如果你无视这样的配置.(你想添加一些"虚假的"选项的所有群体，并允许指数很多的选择，如果"伪造"是不是选择。这是更为复杂的解释，所以我会做到这一请求。)

这是上面sdcvvc的出色答卷简要提及，但可能蒙特卡洛近似足够好？产生N个随机配置（其中N是这样选择自己的实验的功率足够高：我不知道，足以帮助你在这里），然后测试有多少人与您的要求不相容。推断出比重到配置空间的其余部分。

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow