combinations - 找到所有可能存在冲突的组合的数量

Question

我正在尝试解决优化问题，但首先我必须找到 n 个元素的所有可能组合的数量，但要考虑一些冲突。一个可能的例子是:

元素:{1,2,3,4}冲突:{1,2},{3,4}

术语“冲突”是指属于同一冲突集合的数字不得分配到同一组合中。此外，冲突集并不总是不相交的，每个冲突集中的元素总是两个。

直到现在我才发现如何计算所有可能的组合，即2^n。

谢谢。

Answer 1

冲突集可以建模为图中的边。你问的是图中独立顶点集的数量

An independent vertex set of a graph G is a subset of the vertices such that no two vertices in the subset represent an edge of G - http://mathworld.wolfram.com/IndependentVertexSet.html

上面的链接还提到了一种叫做独立多项式的东西，它可以用来计算这些东西——尽管这只有在冲突图有一个很好的结构时才有用。已知确定独立集数量的一般问题是#P-complete(有关此复杂性类别的定义，请参阅 https://en.wikipedia.org/wiki/Sharp-P-complete)，因此您的问题不太可能有简单的答案。在某些情况下，已应用马尔可夫链技术来近似这个数字。参见 http://www.researchgate.net/publication/221590282_Approximately_Counting_Up_To_Four_(Extended_Abstract)