给定一个布尔值的二维数组我想查找所有由至少2列和至少2行组成的模式。这个问题有点接近于找到cliques in a graph。如何在布尔数组中找到模式组？
在下面的例子中，绿色单元表示“真”位，灰色是“假”。模式1包含列1,3,4和5以及行1和2.模式2仅包含列2和列4以及行2,3,4。这背后
经营思路是寻找社交网络用户的不同群体之间的类似图形。在现实世界中，行数可以达到3E7，并且列数可以达到300.
无法真正找出除蛮力匹配以外的解决方案。
请指出问题的正确名称，以便我可以阅读更多内容，或者建议一个优雅的解决方案。
这是（相当于）要求在二分图中大于特定大小的所有bicliques（完全二部分子图）。在这里，行是图的一个部分A的顶点，列是另一个部分B的顶点，并且每当行u，列v处的单元在A中的u \和B中的v \之间存在边是绿色的。
虽然你说你想查找所有模式，但你可能只想找到最大的个 - 也就是说，通过添加更多行或列无法扩展成更大模式的模式。 （否则，对于c> = 2列且r> = 3行的任何模式，您还将返回超过2 ^（c-2）* 2 ^（r-3）个可形成的非最大模式通过删除某些行或列）
但是，即使列出最大模式，假设P！= NP，也可能需要一定的行数和列数的指数。这是因为根据绿色单元的总数寻找最大值（即最大可能）图案的问题，has been proven to be NP-complete：如果可以在多项式时间中列出所有最大图案，那么我们可以简单地这样做，并挑选最大的，从而在多项式时间内解决这个NP完全问题。
谢谢@j_random_hacker专家的回答。现在查看算法：[通过列举最大Bicliques揭示流感株之间的基因组重配[Nagarajan，Kingsford]（http://www.cbcb.umd.edu/~niranjan/papers/NagarajanKingsfordBIBM08.pdf）和[关于在二分法中找到bicliques图表 - 张，菲利普斯，罗杰斯，贝克，切斯勒，兰斯顿]（http://www.biomedcentral.com/1471-2105/15/110） – Serge
很高兴我可以帮助@Serge :) –
如果数组是对称的，并且所有的对角条目都是真的，则必须找到对应于图中派系的对称全真子阵列等等。由于确定最大的集团（或补充中最大的独立集合）是NP难度，所以这个问题也是如此。这并不意味着它不能在实践中完成，但它确实表明您应该提供有关数组特性的更多信息，而不是希望获得快速，通用的算法。 –
究竟是什么模式？我仍然不清楚。 –
@DouglasZare，谢谢你的评论。数组不对称。行代表一个用户，并且这些位对于从研究到研究各不相同的独立属性处于打开状态。即b1“有高等教育”，b2“喜欢页面X”，b3：喜欢页面Y“等等。 JuanLopes by”pattern“我的意思是”开“列的集合，超过2个，适用于2个以上的用户 – Serge