找到所有可能存在冲突的组合的数量
find the number of all possible combinations with conflicts
我正在尝试解决优化问题，但首先我必须找到 n 个元素的所有可能组合的数量，但要考虑到一些冲突。一个可能的例子是：
元素：{1,2,3,4}
冲突：{1,2},{3,4}
"conflict"表示属于同一个冲突集的号码不能分配到同一个组合中。此外，冲突集并不总是不相交的，每个冲突集中的元素总是两个。
直到现在我才发现如何计算所有可能的组合，即2^n。
谢谢。
冲突集可以建模为图中的边。你问的是图中独立顶点集的数量
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
上面的link也指的是一种叫做独立多项式的东西，它可以用来计算这些东西——尽管这只有在冲突图有一个不错的结构。已知确定独立集数量的一般问题是#P-complete（参见https://en.wikipedia.org/wiki/Sharp-P-complete for a definition of this complexity class) so there is little chance that your question has a simple answer. Markov-chain techniques have been applied to approximate this number in some cases. See http://www.researchgate.net/publication/221590282_Approximately_Counting_Up_To_Four_(Extended_Abstract)
我正在尝试解决优化问题，但首先我必须找到 n 个元素的所有可能组合的数量，但要考虑到一些冲突。一个可能的例子是：
元素：{1,2,3,4} 冲突：{1,2},{3,4}
"conflict"表示属于同一个冲突集的号码不能分配到同一个组合中。此外，冲突集并不总是不相交的，每个冲突集中的元素总是两个。
直到现在我才发现如何计算所有可能的组合，即2^n。
谢谢。
冲突集可以建模为图中的边。你问的是图中独立顶点集的数量
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
上面的link也指的是一种叫做独立多项式的东西，它可以用来计算这些东西——尽管这只有在冲突图有一个不错的结构。已知确定独立集数量的一般问题是#P-complete（参见https://en.wikipedia.org/wiki/Sharp-P-complete for a definition of this complexity class) so there is little chance that your question has a simple answer. Markov-chain techniques have been applied to approximate this number in some cases. See http://www.researchgate.net/publication/221590282_Approximately_Counting_Up_To_Four_(Extended_Abstract)