I have Boolean matrix A (called "board") and Boolean matrix B with smaller dimensions (called "pattern"). I am trying to find sub-matrixes C of A such that C has same dimensions as B, and TableImplies[C, B].
Function TableImplies returns true if matrix A piecewise implies matrix B:
TableImplies[A,B]=true if for all i,j (a_ij => b_ij).
Example:
falsePattern = Table[False, {15}, {15}];
truePattern = Table[True, {15}, {15}];
Here TableImplies[falsePattern, truePattern] == True, but TableImplies[truePattern, falsePattern] == False.
I have the following code, but it is not very fast:
tableImplies[a_, b_] := And @@ Flatten@MapThread[Implies, {a, b}, 2]
searchTable[pattern_, board_] :=
Reap[{sizex, sizey} = Dimensions[pattern];
Do[subBoard = board[[i ;; i + sizex - 1, j ;; j + sizey - 1]];
If[tableImplies [subBoard, pattern], Sow[{i, j}]],
{i, 1, 16 - sizex}, {j, 1, 16 - sizey}]][[2]]
board = Table[i != 16 - j , {i, 1, 15}, {j, 1, 15}];
kroneckerPattern = Table[i == j, {i, 1, 2}, {j, 1, 2}];
Timing[Do[searchTable[kroneckerPattern, board], {100}]][[1]]/100
(* 0.00873606 *)
How do improve speed of this calculation? How to improve coding style?
UPDATE: Michael's answer seems to only search for specified sub-matrix inside the given matrix, instead of returning sub-matrixes, that piecewise imply given pattern.
I added examples to the beginning of question to better explain what I wanted (see truePattern, falsePattern and how they should be related to each other when using TableImplies). I guess I should have been more clear from the beginning.
This compares my algorithm(searchTable) to Michael's (Position[...]). They are clearly not equivalent:
searchTable[truePattern, falsePattern];
Out: {{{1, 1}}}
searchTable[falsePattern, truePattern]
Out: {}
Position[Partition[truePattern, Dimensions@falsePattern, 1], falsePattern]
Out: {}
Position[Partition[falsePattern, Dimensions@truePattern, 1], truePattern]
Out: {}
Update 2: I thought I should be more specific in formulating my question. Details matter. As I said before, I want to know, how should this algorithm could be made faster. It is important to mark that the board (containing matrix) will be always of constant size (15x15), but the pattern (searched sub-matrix) will be of varying dimensions, but always smaller than the board.
This is relevant because for example in link provided by ssch, https://stackoverflow.com/questions/8364804/a-fast-implementation-in-mathematica-for-position2d, the matrixes are very large and the hard part is finding the position. In my case the number of possible positions is not very large (at most 225), but the slow part is to show whether the pattern matches the board or not. Maybe, if this whole problem could be re-written as boolean expression, that Mathematica could try to solve? Would this approach be faster?
Another important note is that the pattern will very likely contain a lot of "True"s in my application. Could this be used to make the algorithm faster? For example, if the pattern contains only 1 False, then the problem is basically finding all instances of "False"s on the board. If the pattern contains more of "False", then the problem still boils down to Boolean expression, but not to an particularly easy one.
PS: If my question is partly about algorithms and partly about programming Mathematica, is it correct of me to post this question here? Maybe I should just first ask some algorithms-related StackExchange Q&A for an algorithm and then ask here for how to program this algorithm effeciently in Mathematica? I just thought that maybe Mathematica's potential for symbolic evaluation could lead to algorithms not thinkable in functional programming languages, which is why I asked directly here :)