3
$\begingroup$

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 :)

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
7
+500
$\begingroup$

String matching works a little better. Think of each row in the board as a string on the alphabet {"0", "1"}. The "pattern" is a set of instructions to look for particular configurations of "0" on the board, because a presence of a "1" in the pattern is no restriction at all and a "0" in the pattern means there must be a corresponding "0" on the board. Thus, we first find where the lines of the pattern are substrings of the rows of the board, and then check for consistency: if the first line of the pattern matches line $j$ of the board, then the second line of the pattern must match line $j+1$ in the same position, etc.

I found it convenient to assume the input arrays contain zeros and ones instead of falses and trues:

search[board_, pattern_] := 
  Module[{n = Length[board], m = Length[pattern], sBoard, sPattern, p, test, s},
   sBoard = IntegerString[FromDigits[#, 2], 2, n] & /@ board;
   sPattern = IntegerString[FromDigits[#], 2, m] & /@ pattern;
   p = StringExpression @@@ (pattern /. {1 -> _, 0 -> "0"});
   test = Outer[First /@ StringPosition[##] &, sBoard, p];
   s = Intersection @@@ (Table[
        Transpose[test][[i, i ;; n - m + i]], {i, 1, m}] // Transpose);
   {#, s[[#]]} & /@ Flatten[Position[s, Except[{}], {1}, Heads -> False]]
   ];

This function returns a list of elements of the form $\{i, \{j_1, j_2, \ldots, j_{k_i}\}\}$ where each $(i, j_l)$, $1 \le l \le k_i$, marks the upper left corner of a match. When using Boolean arrays, first apply Boole to the arguments, thus:

search[Boole[board], Boole[kroneckerPattern]]

$\{\{1,\{14\}\},\{2,\{13\}\},\{3,\{12\}\},\{4,\{11\}\},\{5,\{10\}\},\{6,\{9\}\},\{7,\{8\}\},\{8,\{7\}\},\{9,\{6\}\},\{10,\{5\}\},\{11,\{4\}\},\{12,\{3\}\},\{13,\{2\}\},\{14,\{1\}\}\}$

On this machine running MMA 8.0, it's twice as fast as the search using TableImplies. The timing is conservative in that all the pre-processing of board (to turn it into an array of strings) is repeated for each pattern; in practice this is unneeded. No effort has been made to optimize this code, so by avoiding some unnecessary transformations or streamlining some of them it might go a little faster.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I will do some Timing tests and try to understand Your code and then I likely will accept it :) $\endgroup$
    – Rauni
    Apr 29, 2013 at 20:19
8
$\begingroup$

It seems I misunderstood the question. Here's an update, which is a considerable improvement, too. It relies on Implies[x, y] being equivalent to Boole[x] (1 - Boole[y]) == 0.

falsePattern = Table[False, {15}, {15}];
truePattern = Table[True, {15}, {15}];
SeedRandom[1];
randomPattern = RandomChoice[{True, False}, {15, 15}];

impliesPosition[board_, pattern_] := 
  Position[ListConvolve[1 - Reverse[pattern, {1, 2}], board], 0, {2}]

impliesPosition[Boole@randomPattern, Boole@randomPattern[[1 ;; 3, 1 ;; 3]]]
  (* {{1, 1}, {2, 3}, {3, 11}, {4, 11}, {4, 12}, {5, 8}, {5, 9}, {5, 10}, {5, 11},
      {6, 11}, {7, 9}, {8, 12}, {8, 13}, {10, 8}, {11, 4}, {11, 9}, {12, 6},
      {13, 2}, {13, 3}, {13, 11}} *)

Testing (with the @Rauni's searchTable, searchTable2 and @whuber's search):

With[{A = randomPattern, B = falsePattern[[1 ;; 2, 1 ;; 2]]},
  First @ searchTable[B, A] ==
  First @ searchTable2[B, A] == 
  Flatten[Thread /@ search[Boole@A, Boole@B], 1] == 
  impliesPosition[Boole@A, Boole@B]
 ]
  (* True *)

Timings, slowest to fastest:

With[{A0 = randomPattern, B0 = falsePattern[[1 ;; 2, 1 ;; 2]]},
 With[{A = Boole@A0, B = Boole@B0},
  {First @ Timing @ Do[ searchTable2[B0, A0],  {1000}],
   First @ Timing @ Do[ searchTable[B0, A0],   {1000}],
   First @ Timing @ Do[ search[A, B],          {1000}],
   First @ Timing @ Do[ impliesPosition[A, B], {1000}]}
  ]]
  (* {15.826409, 1.580452, 0.203864, 0.027979} *)

(Timings vary with the size of the pattern matrix, as well as the size of the board.)

Like @whuber's search, it is more convenient to work with impliesPosition if the matrices are converted to 0/1 matrices with Boole.

Original suggestion:

Position[Partition[board, Dimensions@kroneckerPattern, 1], kroneckerPattern]

It returns the same set of indices, but without an extra set of {}:

Position[Partition[board, Dimensions@kroneckerPattern, 1], kroneckerPattern] ==
 First@searchTable[kroneckerPattern, board]
  (* True *)

Comparison of speed:

Timing[Do[searchTable[kroneckerPattern, board], {100}]]
  (* {0.157708, Null} *)

Timing[Do[
  Position[Partition[board, Dimensions@kroneckerPattern, 1], kroneckerPattern], {100}]]
  (* {0.015330, Null} *)
Improve this answer
$\endgroup$
5
  • $\begingroup$ I wanted something different; see update on my question. But getting rid of extra set of {} is good thing, it annoyed me :) PS. What does the parameter "1" do in function call Partition[..., ..., 1]? I did not understand from documentation and the result is same if I just remove the 1. Would be thankful for explanation :) $\endgroup$
    – Rauni
    Apr 29, 2013 at 16:26
  • $\begingroup$ I understood now with help of documentation, what Partition[..., ..., 1] does - it offsets the taking of partition by 1. But shouldn't it be Partition[..., ..., {1,1}] then, because we want to offset by 1 at both levels? $\endgroup$
    – Rauni
    Apr 29, 2013 at 20:20
  • $\begingroup$ @Rauni I think Partition[..., 1] and Partition[..., {1, 1}] are equivalent here. See the third example (the last Basic Example) in the documentation $\endgroup$
    – Michael E2
    Apr 30, 2013 at 3:59
  • $\begingroup$ OK, understood. $\endgroup$
    – Rauni
    Apr 30, 2013 at 14:45
  • $\begingroup$ +1 That's a very clever use of convolution: it will be hard to beat for speed. $\endgroup$
    – whuber
    Apr 30, 2013 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.