基于大型真值表生成所有组合的算法方法
如果这个问题在其他地方得到了回答，我深表歉意，但我还没有使用我有限的算法术语找到它。 ；）
我的情况是这样的 - 我有数量可变的数据元素，每个数据元素都已针对彼此的数据元素进行了测试以确定兼容性。兼容性存储在相当于二维数组（真值表？）中。我的目标是生成这些数据元素的所有可能组合，其中组合中的每个元素都与其他元素兼容。
例如，如果元素 1（共 4 个）与元素 2 和 4 兼容，元素 2 与 1、3 和 4 兼容，元素 3 与 2 兼容，元素 4 与 1 和 2 兼容，我的真值表将看起来像：
1) {1,1,0,1}
2) {1,1,1,1}
3) {0,1,1,0}
4) {1,1,0,1}
我想要的组合是：
1,2,4
1,2
1,4
1
2,3
2,4
2
3
4
我的方法在许多情况下效果很好，但有时当元素数量超过 5000 时会严重陷入困境，具体取决于数据集。我的第二个挑战是确定将执行时间从 5 秒延长到 3 小时的模式...
仅通过查看布尔数组，我只是觉得必须有一个更简单的解决方案 - 一种以某人命名的算法，也许。正如您可能从上面推断的那样，我不一定知道如何提出这个问题。 ；）
感谢您的宝贵时间！
I apologize if this has been answered elsewhere, but I have yet to find it using my limited algorithmic terminology. ;)
My situation is this - I have a variable number of data elements, each of which has been tested against each other data element to determine compatibility. The compatibilities are stored in the equivalent to a 2-dimensional array (truth table?). My goal is to generate all possible combinations of these data elements, where every element within the combination is compatible with each other element.
For example, if element 1 (of 4) was compatible with elements 2 and 4, and element 2 was compatible with 1, 3 and 4, element 3 was compatible with 2 and element 4 was compatible with 1 and 2, my truth table would look something like:
1) {1,1,0,1}
2) {1,1,1,1}
3) {0,1,1,0}
4) {1,1,0,1}
The combinations that I want from this would be:
1,2,4
1,2
1,4
1
2,3
2,4
2
3
4
My approach works well in many situations, but is sometimes bogged down badly when the number of elements exceeds 5000, depending on the data sets. My secondary challenge is to determine the pattern that brings execution time up from 5 seconds to 3 hours...
Just from looking at the boolean array, I just feel like there MUST be an easier solution out there - an algorithm named after somebody, maybe. As you might infer from the above, I don't necessarily know how to ask the question. ;)
Thanks for your time!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为您拥有的是“邻接矩阵”而不是真值表，并且您正在寻找以邻接矩阵表示的图的所有“完全连接的子图”。如果没记错的话，完全连接的子图也被称为“派系”。我不太确定你在寻找什么；正如一位早期受访者指出的那样，您的文字和矩阵之间存在一些差异。
用谷歌搜索一下这些术语；现在对我来说，从我的头脑或图书馆中挖掘这些东西已经太晚了。
请注意，您的图表是对称的，也就是说，如果“1 与 2 兼容”，那么必然“2 与 1 兼容”。现在，您的数据存储需求减少了一半（使它们变得更加复杂，存储矩阵的上半部分或下半部分通常比它节省的空间更令人费解）。我还认为你应该沿着主对角线有 1，以表达“1 与 1 兼容”的想法。我怀疑最终你会得到一些只与自身兼容的元素。
遗憾的是，在图中查找派系是 NP，但对于仅包含 5000x5000 元素的矩阵，暴力朴素算法在编译语言中不应花费太长时间。
问候
马克
I think that what you have is an 'adjacency matrix' not a truth table and that you are looking for all the 'fully connected subgraphs' of the graph of which the adjacency matrix is a representation. Fully connected subgraphs are also known, if memory serves, as 'cliques'. I'm not terribly sure about what you are looking for; as one of the earlier respondents indicated there are some discrepancies between your words and your matrix.
Do some googling around on those terms; right here right now it's too late for me to dig this stuff out of either my head or my library.
Note that your graph is symmetric, that is if '1 is compatible with 2' then necessarily '2 is compatible with 1'. Now that's halved your data storage requirements (made them more complex, storing the upper or lower half of the matrix is often more mind-bending than the space it saves warrants). I think also that you should probably have 1s along the main diagonal, to express the idea that '1 is compatible with 1'. Eventually, I suspect, you'll have some elements which are only compatible with themselves.
Finding cliques in a graph is, sadly, NP, but for matrices of only 5000x5000 elements a brute-force naive algorithm shouldn't take too long in a compiled language.
Regards
Mark
您基本上是在尝试将表达式简化为析取范式。一般来说，这个问题是NP完全问题。对不起。 ^_^
You're basically trying to reduce an expression to disjunctive normal form. In general, this problem is NP-complete. Sorry. ^_^