问题描述
鉴于布尔值，我想找到的所有模式，包括至少2列和至少2行的二维数组。现在的问题是有点接近找到派系在图表。
Given a 2D array of Boolean values I want to find all patterns that consist of at least 2 columns and at least 2 rows. The problem is somewhat close to finding cliques in a graph.
在下面的例子中绿色细胞重新present真位，灰色都是假。图案1包含COLS 1,3,4和5和行1和2图案2只包含列2和4，和行2,3,4
In the example below green cells represent "true" bits, greys are "false". Pattern 1 contains cols 1,3,4 and 5 and rows 1 and 2. Pattern 2 contains only columns 2 and 4, and rows 2,3,4.
这背后的经营理念是寻找各个群体的社交网络用户之间的相似性模式。在现实世界中的行数可以达到3E7，和列数高达300
Business idea behind this is finding similarity patterns among various groups of social network users. In real world number of rows can go up to 3E7, and the number of columns up to 300.
不能真正弄明白比蛮力匹配其他的解决方案。
Can't really figure out a solution other than brute force matching.
请指教问题的正确名字，这样我就可以多读，或建议一个完美的解决方案。
Please advice the proper name of the problem, so I could read more, or advice an elegant solution.
推荐答案
这是（相当于）要求所有的（完全偶子图）超过一定尺寸的二分图大。这里，行是图的一个部分A的顶点，和列是另一部分B的顶点，并有一个边之间U \在甲和v \ B中，每当在排U，V列的单元是绿色的。
This is (equivalent to) asking for all bicliques (complete bipartite subgraphs) larger than a certain size in a bipartite graph. Here the rows are the vertices of one part A of the graph, and the columns are the vertices of the other part B, and there is an edge between u \in A and v \in B whenever the cell at row u, column v is green.
虽然你说你要找到所有的模式，你可能只需要才发现的最大的的 - 也就是说，不能被扩展为更大的模式通过添加更多的行或列模式。 （否则，对于采用c> = 2列并且r> = 3行任何模式，则还取回大于2 ^（C-2）*可以形成2 ^（R-3）非最大型态通过删除部分的行或列的。）
Although you say that you want to find all patterns, you probably only want to find only maximal ones -- that is, patterns that cannot be extended to become larger patterns by adding more rows or columns. (Otherwise, for any pattern with c >= 2 columns and r >= 3 rows, you will also get back the more than 2^(c-2)*2^(r-3) non-maximal patterns that can be formed by deleting some of the rows or columns.)
但是，即使刚上市的最大的图案可能需要一段时间的指数以行和列的数目，若设P！= NP。这是因为，查找的最大的（即最大-可能）图案，在绿色细胞的总数而言，：如果有可能，列出在多项式时间内所有极大的模式，那么我们可以简单地这样做，并挑选规模最大，从而解决在多项式时间这个NP完全问题。
But even listing just the maximal patterns can take time exponential in the number of rows and columns, assuming that P != NP. That's because the problem of finding a maximum (i.e. largest-possible) pattern, in terms of the total number of green cells, has been proven to be NP-complete: if it were possible to list all maximal patterns in polynomial time, then we could simply do so, and pick the largest, thereby solving this NP-complete problem in polynomial time.
这篇关于如何找到图案组布尔数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！