7
$\begingroup$

( This question is related but does not ( fully ) answer my questions. - Finding the position of similar elements in a matrix )

I have not written code yet, I am in the design phase of code for the following problem. I will illustrate the problem with a 6-by-6 matrix in the form of inputs and expected outputs and a commentary. In practice the matrices will be in the order of 2000 by 2000 ( if a solution is realistic ).

I want to scan a matrix for blocks ( rows, columns, submatrix ) containing similar elements ( in this particular case: equal elements ). When such a block is found I want to know: 1) topleft index 2) bottom right index 3) submatrix of elements 4) the matrix with similar elements set to Null

Input:

 {
   {1, 2, 1, 4, 5, 6},
   {1, 2, 1, 1, 2, 3},
   {1, 2, 1, 7, 8, 9},
   {4, 4, 4, 4, 4, 4},
   {4, 4, 4, 4, 4, 4},
   {4, 4, 4, 4, 4, 4}} // MatrixForm

Output:

 {{1,1},{3,1}}     (* top left , bottom right indices*)
 {{1},{1},{1}}     (* sub matrix *)

 {{1,2},{3,2}}     
 {{2},{2},{2}}

 {{1,3},{3,3}}     
 {{1},{1},{1}}

 {{2,3},{2,4}}     
 {{1, 1}}

 {{4,1},{6,6}}     
 {
   {4, 4, 4, 4, 4, 4},
   {4, 4, 4, 4, 4, 4},
   {4, 4, 4, 4, 4, 4}}


  (* what remains of the matrix with similar elements Nulled *)
 {  
  {Null, Null, Null, 4, 5, 6},
  {Null, Null, Null, Null, 2, 3},
  {Null, Null, Null, 7, 8, 9},
  {Null, Null, Null, Null, Null, Null},
  {Null, Null, Null, Null, Null, Null},
  {Null, Null, Null, Null, Null, Null}} // MatrixForm

Question: I am basically interested in how to select a submatrix with similar elements, in the form of a code snippet, a clear explanation of the code, why this particular method was chosen and if you are aware of any other methods that could be tried to give the same result.

Note: Similarity of elements in this case is that two elements in a row or column are equal, but this should not be hardcoded a pure function should be provided to explain what similarity means, although the default case could be set to the above example.

This example :

 {{1, 1, 1, 1, 1}, 
  {1, 1, 1, 1, 1}, 
  {1, 1, 1, 2, 2},
  {1, 1, 1, 2, 2}}

seems to have multiple solutions. It does not really matter which one to choose as long as no doubles remain in the final matrix. So a 4x3 with 1s and a 2x2 and a 2x2 with 2swith 1s is ok but also a 2x5 with 1s and a 2x3 with 1s and a 2x2 with 2s is ok.

$\endgroup$
  • 1
    $\begingroup$ I don't have time right now to write an answer, but I think a good direction would be to use ClusteringComponents for the "segmentation", and then use that to find the maximal rectangles that one can fit in each component. $\endgroup$ – yohbs Jul 12 '15 at 9:55
  • 1
    $\begingroup$ What about conflicting submatrix blocks of the form {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 2, 2}, {1, 1, 1, 2, 2}} // MatrixForm? Should both the submatrices be returned but not the single rows/columns? $\endgroup$ – glS Jul 12 '15 at 10:57
  • 3
    $\begingroup$ What have you done/tried? I don't see a real question here, just a specification for "do my work for me...". $\endgroup$ – ciao Jul 12 '15 at 17:26
  • 5
    $\begingroup$ I'm voting to close this question as off-topic because it appears to be a work order and not a question regarding some particular difficulty or problem using Mathematica. $\endgroup$ – ciao Jul 12 '15 at 18:15
  • 3
    $\begingroup$ @ndroock1: This is an np-hard problem (first shown by Mathies IIRC in the eighties). There's a fine book called "Pattern Matching Algorithms" by Galil that covers common submatrix matching, perhaps you can find a copy in a local Uni library? $\endgroup$ – ciao Jul 12 '15 at 19:27
1
$\begingroup$

Here is an attempt. It most probably won't do for large matrices due to the inefficient algorithm, but it seems to work on smaller examples:

enlargeBlock[matrix_List, blockStart_List, blockEnd_List] := Which[
  (* enlarge in the down-right-diagonal direction, if possible *)
  And @@ Thread[blockEnd < Dimensions@matrix] &&
   matrix[[blockStart[[1]] ;; blockEnd[[1]] + 1, 
     blockStart[[2]] ;; blockEnd[[2]] + 1]] == 
    ConstantArray[matrix[[Sequence @@ blockStart]], 
     blockEnd - blockStart + 2],
  blockEnd + 1,
  (* enlarge in the down-vertical direction, if possible *)
  blockEnd[[1]] < First@Dimensions@matrix &&
   matrix[[blockStart[[1]] ;; blockEnd[[1]] + 1, 
     blockStart[[2]] ;; blockEnd[[2]]]] == 
    ConstantArray[
     matrix[[Sequence @@ blockStart]], {blockEnd[[1]] - 
       blockStart[[1]] + 2, blockEnd[[2]] - blockStart[[2]] + 1}],
  {blockEnd[[1]] + 1, blockEnd[[2]]},
  (* enlarge in the right-horizontal direction, if possible *)
  blockEnd[[2]] < Last@Dimensions@matrix &&
   matrix[[blockStart[[1]] ;; blockEnd[[1]], 
     blockStart[[2]] ;; blockEnd[[2]] + 1]] == 
    ConstantArray[
     matrix[[Sequence @@ blockStart]], {blockEnd[[1]] - 
       blockStart[[1]] + 1, blockEnd[[2]] - blockStart[[2]] + 2}],
  {blockEnd[[1]], blockEnd[[2]] + 1},
  True,
  blockEnd
  ]
findBiggestBlock[matrix_List, blockStart_List] := 
 FixedPoint[enlargeBlock[matrix, blockStart, #] &, blockStart]
findBlocks[matrix_List] := 
 Block[{mask = ConstantArray[1, Dimensions@matrix]},
     Do[
      If[mask[[i, j]] == 1,
       With[{blockEnd = findBiggestBlock[matrix, {i, j}]},
        Sow@
         Association[start -> {i, j}, end -> blockEnd, 
          elements -> 
           matrix[[i ;; blockEnd[[1]], j ;; blockEnd[[2]]]]];
        mask[[i ;; blockEnd[[1]], j ;; blockEnd[[2]]]] = 0
        ]
       ],
      {i, First@Dimensions@matrix},
      {j, Last@Dimensions@matrix}
      ]
     ] // Reap // Last // Last

And as an usage example:

(m = {{1, 2, 1, 4, 5, 6}, {1, 2, 1, 1, 2, 3}, {1, 2, 1, 7, 8, 9}, {4, 
     4, 4, 4, 4, 4}, {4, 4, 4, 4, 4, 4}, {4, 4, 4, 4, 4, 
     4}}) // MatrixForm
findBlocks[m]

which gives:

enter image description here

$\endgroup$
  • $\begingroup$ Thank you, - Knuth allegedly said that optimization comes last. This is a start! Please read the comment section about what @ciao said about the problem. I will work on this again this evening UTC+1. $\endgroup$ – nilo de roock Jul 13 '15 at 7:13
  • $\begingroup$ Also: This ( I referred to it in the question ) mathematica.stackexchange.com/questions/50578/… has a solution that comes very, very close and is compact. $\endgroup$ – nilo de roock Jul 13 '15 at 7:17
  • $\begingroup$ @ndroock1 I saw that post, but I don't think it's very similar to this problem. The hard thing here is to find elements which are "similar" and close. It's the last constraint that forces the use of more elaborated code (and way more computational time). $\endgroup$ – glS Jul 13 '15 at 7:46

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