How to find all the sub square matrices of this matrix

Question

I have a 300*300 matrix. I want to find all the sub square matrices of this matrix such that all the elements of each matrix have the same value.

For eg: Consider a matrix

1 4 5 6 7 8 5 3 4
3 7 7 9 4 2 2 2 5
8 7 7 8 5 3 2 2 1
6 6 7 8 6 3 1 2 3
6 6 8 3 1 1 4 9 0
3 3 3 6 1 1 2 2 0
3 3 3 4 5 6 0 9 1
3 3 3 4 5 6 2 1 0

so the sub matrix with all equal values are 7 7 3 3 3 6 6 1 1 2 2
7 7 3 3 3 6 6 1 1 2 2
3 3 3

Can anyone give me some idea how to do this in C#

Divya · Answer

hi can u pls help me with dis problem: Using Dynamic programming approach write a O(n^2) algorithm for following. pls reply asap.its URGENT given a large image of a chip you have to find the two largest non-overlapping square blocks which are still unused. The image of the chip is given to you as follows: 5 6 R F F R R F F F F F F F R R F F F F F F F F F F F F F F F F The numbers 5 and 6 are the number of rows and columns respectively and R means reserved and F means free. In this case the largest square is F F F F F F F F F F F F F F F F and the second largest (non-overlapping with the previous one) is F F F F In general the selection of the largest square conditions the choice and the size of the second since the second largest cannot overlap with the largest. If there are multiple largest squares (i.e. several squares with the same area) your program should choose the one that allows the second largest to be as large as possible. Sample Input 2 5 6 R F F F F F F F R R F F R R R F F F F F F F F F F F F F F F 5 5 R R R R R F R R R R F R F R R R R R R R R R R R R For each data set in the input file print on a separate line on the standard output the area of the two largest unused non-overlapping square (separated by a space). Sample Output (corresponding to the sample input above) 9 4 1 1 Thanks

Alan · Answer

Sorry I hadn't picked up on the word 'rectangular' there :) Well I'm sure it's possible to figure that out both in safe and unsafe code but it's going to be very slow compared to the square submatrix case because for every submatrix we're currently examining of size n x n for the 300 x 300 case you'd need to examine just under 2 x n rectangular submatrices. You'd therefore be talking of an execution time of several minutes rather than a few seconds. There may be clever algorithms available which can cut the time used by 'brute force' methods but I'm afraid I don't know of any as it's a long time since I did any serious mathematics.

aakash malhotra · Answer

I appreciate the effort its pretty fast... but my concern was to detect rectangular sub matices it still detects square matrices like 2*2 3*3 4*4 and so on..... wat bout sub matrices of order 4*5 3*6 m*n where m and n are not equal. Is it possible to detect such matrices...??

Alan · Answer

Yes. In fact I've recoded the GenerateSubmatrices() method below using 'unsafe' code - nothing else needs changing. My very rough tests on much smaller matrices suggest that you may be able to knock a couple of seconds off the 7 second execution time for the 300 * 300 matrix the time saving coming from not having to check that the array accesses (of which there are a lot) are within bounds. As we're reasonably sure now that this won't cause a memory leak the code should be safe to use provided I haven't made a blunder converting the array accesses to pointer accesses: unsafe static List GenerateSubmatrices(int[] matrix) { List smiList = new List (); int rows = matrix.GetLength(0); int cols = matrix.GetLength(1); int maxSize = (rows == cols) ? rows - 1 : Math.Min(rows cols); if (maxSize bool[] used = new bool[rows cols]; // all false initially int first = 0; bool isSame = false; fixed(int* pMatrix = &matrix[00]) { fixed(bool* pUsed = &used[00]) { int* pm = pMatrix; bool* pu = pUsed; for(int size = maxSize; size > 1; size--) { for(int x = 0; x { for(int y = 0; y { first = pm[x * cols + y]; isSame = true; for(int sx = x; sx { for(int sy = y; sy { int pos = sx * cols + sy; if (pu[pos] || first != pm[pos]) { isSame = false; goto next; } } } next: if (isSame) { smiList.Add(new SubmatrixInfo(x y  size  first)); for(int ux = x; ux { for(int uy = y; uy { pu[ux * cols + uy] = true; } } } } } } // remove any submatrix from list which is not isolated bool isIsolated = false; SubmatrixInfo smi; for (int i = smiList.Count - 1; i >= 0; i--) { isIsolated = true; smi = smiList[i]; if (smi.Y > 0) { for(int ix = smi.X; ix { if(pm[ix * cols + smi.Y - 1] == smi.Value) { isIsolated = false; goto finish; } } } if (smi.Y { for(int ix = smi.X; ix { if(pm[ix * cols + smi.Y + smi.Rows] == smi.Value) { isIsolated = false; goto finish; } } } if (smi.X > 0) { for(int iy = smi.Y; iy { if(pm[(smi.X - 1) * cols + iy] == smi.Value) { isIsolated = false; goto finish; } } } if (smi.X { for(int iy = smi.Y; iy { if(pm[(smi.X + smi.Rows) * cols + iy] == smi.Value) { isIsolated = false; goto finish; } } } // now deal with top diagonal elements if (smi.X > 0 && smi.Y > 0) { if(pm[(smi.X - 1) * cols + smi.Y - 1] == smi.Value) { isIsolated = false; goto finish; } } if (smi.X > 0 && (smi.Y { if(pm[(smi.X - 1) * cols + smi.Y + smi.Rows] == smi.Value) { isIsolated = false; goto finish; } } // finally deal with bottom diagonal elements if (smi.Y > 0 && (smi.X { if(pm[(smi.X + smi.Rows) * cols + smi.Y - 1] == smi.Value) { isIsolated = false; goto finish; } } if ((smi.X { if(pm[(smi.X + smi.Rows) * cols + smi.Y + smi.Rows] == smi.Value) { isIsolated = false; goto finish; } } finish: if (!isIsolated) smiList.RemoveAt(i); } } } return smiList; }

aakash malhotra · Answer

can we also detect rectangular sub matrices of equal value using this???

Alan · Answer

Marking a piece of code as 'unsafe' in C# enables you to use unmanaged pointers in that code with all the attendant risks. So it's a bit like using C code in C#. Because of this it can only be run in a fully trusted environment. So basically you can try and quicken up any piece of C# code by using pointer manipulations including this one. However in my experience improvements are usually only marginal and so it's seldom worth the effort.

aakash malhotra · Answer

hmmm... can we also detect rectangular sub matrices of equal value using this???

Alan · Answer

No I don't think multi-threading would help. We've only got the one 'natural' method here and I can't really see how you could split off some of the processing into a sub-method running on a separate thread without the need for the first thread to wait for the second thread to finish. Given the overhead of an additional method call and context switches by the OS it's therefore going to be quicker to run it on a single thread. To be honest I'm pleasantly surprised that it can process a 300 x 300 matix in as little as 7 seconds. You might be able to shave a bit off that by rewriting it in 'unsafe' code which would remove array bounds checking and then manipulate the arrays with pointers but otherwise I think it's as fast now as we're likely to get it.

aakash malhotra · Answer

yes this works..... I was wondering if multi threading will be a good idea to reduce execution time or will it make the code more complex. It takes about 7 sec for finding the sub matrices of a 300*300 matrix. I need to access 800 such matrices. Do you think using multithreading will help??

Alan · Answer

If you want to isolate on the adjoining diagonal elements as well then you'll need to deal with the four elements individually: // now deal with top diagonal elements if (smi.X > 0 && smi.Y > 0) { if(matrix[smi.X - 1 smi.Y - 1] == smi.Value) { isIsolated = false; goto finish; } } if (smi.X > 0 && (smi.Y { if(matrix[smi.X - 1 smi.Y + smi.Rows] == smi.Value) { isIsolated = false; goto finish; } } // finally deal with bottom diagonal elements if (smi.Y > 0 && (smi.X { if(matrix[smi.X + smi.Rows smi.Y - 1] == smi.Value) { isIsolated = false; goto finish; } } if ((smi.X { if(matrix[smi.X + smi.Rows smi.Y + smi.Rows] == smi.Value) { isIsolated = false; goto finish; } }

aakash malhotra · Answer

Just one more question... how to take care of the diagonal elements. I mean how to detect the diagonally neighboring elements for isolated sub matrices. I wrote the code but its not working: if (smi.X > 0 && smi.Y > 0 && smi.X { for (int iy = smi.Y; iy { if (matrix[smi.X - 1 iy - 1] == smi.Value || matrix[smi.X - 1 iy + 1] == smi.Value) { isIsolated = false; goto finish; } } } if (smi.X > 0 && smi.Y > 0 && smi.X { for (int iy = smi.Y; iy { if (matrix[smi.X + smi.Rows iy - 1] == smi.Value || matrix[smi.X + smi.Rows iy + 1] == smi.Value) { isIsolated = false; goto finish; } } }

Alan · Answer

It is a great platform and even for computationally intensive work managed code is a lot quicker than many C/C++ programmers think provided you choose the right algorithm use structs rather than classes throw in the occasional 'goto' and so forth :)

aakash malhotra · Answer

Thanks a lot. It is working perfectly fine. I appreciate your time and concern. This initiative from your side has encouraged me to learn in depth about C#. It is a great platform.

Alan · Answer

OK I think all we need to do is to get the list of disjoint submatrices as before and then remove those which are not isolated from the list. The effect on execution time should be minimal: using System; using System.Collections.Generic; // Information for same value square submatrix struct SubmatrixInfo { public readonly int X; // x coordinate in parent of top left element public readonly int Y; // y coordinate in parent of top left element public readonly int Rows; // number of rows and hence columns in submatrix public readonly int Value; // common value of elements public SubmatrixInfo(int x int y int rows int value) { X = x; Y = y; Rows = rows; Value = value; } public override string ToString() { return String.Format(At [{0} {1}] size {2} x {2} value {3} X Y Rows Value); } } class Program { static void Main() { int[] matrix = new int[] { {1 3 4 5 5 5 7 7} {2 3 4 5 5 5 4 3} {9 8 7 7 7 4 3 2} {2 4 7 7 7 6 6 6} {3 2 7 7 7 5 3 1} {9 8 4 3 2 5 6 5} {3 4 4 5 2 1 0 9} {2 4 4 6 3 2 1 9} }; List smiList = GenerateSubmatrices(matrix); int count = 0; foreach(SubmatrixInfo smi in smiList) { Console.WriteLine(smi); count++; if(count % 20 == 0) { Console.WriteLine(
Press any key to continue ...
); Console.ReadKey(); } } } static List GenerateSubmatrices(int[] matrix) { List smiList = new List (); int rows = matrix.GetLength(0); int cols = matrix.GetLength(1); int maxSize = (rows == cols) ? rows - 1 : Math.Min(rows cols); if (maxSize bool[] used = new bool[rows cols]; // all false initially int first = 0; bool isSame = false; for(int size = maxSize; size > 1; size--) { for(int x = 0; x { for(int y = 0; y { first = matrix[x y]; isSame = true; for(int sx = x; sx { for(int sy = y; sy { if (used[sx sy] || first != matrix[sx sy]) { isSame = false; goto next; } } } next: if (isSame) { smiList.Add(new SubmatrixInfo(x y  size  first)); for(int ux = x; ux { for(int uy = y; uy { used[ux uy] = true; } } } } } } // remove any submatrix from list which is not isolated bool isIsolated = false; SubmatrixInfo smi; for (int i = smiList.Count - 1; i >= 0; i--) { isIsolated = true; smi = smiList[i]; if (smi.Y > 0) { for(int ix = smi.X; ix { if(matrix[ix smi.Y - 1] == smi.Value) { isIsolated = false; goto finish; } } } if (smi.Y { for(int ix = smi.X; ix { if(matrix[ix smi.Y + smi.Rows] == smi.Value) { isIsolated = false; goto finish; } } } if (smi.X > 0) { for(int iy = smi.Y; iy { if(matrix[smi.X - 1 iy] == smi.Value) { isIsolated = false; goto finish; } } } if (smi.X { for(int iy = smi.Y; iy { if(matrix[smi.X + smi.Rows iy] == smi.Value) { isIsolated = false; goto finish; } } } finish: if (!isIsolated) smiList.RemoveAt(i); } return smiList; } } This just returns the 3 x 3 submatrix of 7's as the two 2 x 2 submatrices are not isolated. Incidentally the 15 x 15 matrix returned no results as none of the 9 disjoint submatrices are isolated.

aakash malhotra · Answer

Mind Blowing my friend. You have actually put it down in the simplest way. Thanks a lot. The execution time is exceptional. But the problem of isolated matrices still remain. Is there a way by which I can access the neighboring elements of each square sub matrix to check whether it has a neighboring element which is of the same value as that of the sub matrix. Just to ensure I get distinct isolated square matrix which has no neighboring element same as its own. For eg: 6 8 5 2 1 0 9 7 7 7 7 8 3 7 7 7 7 0 1 7 7 7 7 8 3 7 7 7 7 5 9 4 4 6 2 9 In the above matrix the 4*4 matrix of 7's is an isolated matrix since there are no neighboring 7's.(no extra one or more '7''s surrounding the sub matrix. Please help this will be the final stage. I will appreciate your concern.

Alan · Answer

I think I must have been half asleep yesterday as there are in fact nine mutually exclusive submatrices with the same value in the 15 x 15 matrix not four! They are: At [0 0] 11 x 11 value 222 At [0 11] 4 x 4 value 222 At [4 11] 4 x 4 value 222 At [11 0] 4 x 4 value 222 At [11 4] 4 x 4 value 222 At [11 8] 3 x 3 value 222 At [11 12] 3 x 3 value 206 At [9 11] 2 x 2 value 214 At [9 13] 2 x 2 value 214 As it's clear that the previous approach wasn't working and was too slow anyway I've rethought the problem and come up with a much simpler and faster non-recursive algorithm which compared to the last one was almost trivially easy to code :) The new algorithm doesn't need any final sorting or filtering and works with rectangular as well as square 'parent' matrices. Basically I'm just searching iteratively now for all submatrices from the biggest size downwards but I've introduced a bool array which keeps track of whether particular elements in the parent matrix have been used before or not and so there's no longer any problems with duplicated or overlapping submatrices.The biggest matrix I've tested it on is the 15 x 15 one but I hope that the running time for even your 300 x 300 matrix will be more acceptable now as well: using System; using System.Collections.Generic; // Information for same value square submatrix struct SubmatrixInfo { public readonly int X; // x coordinate in parent of top left element public readonly int Y; // y coordinate in parent of top left element public readonly int Rows; // number of rows and hence columns in submatrix public readonly int Value; // common value of elements public SubmatrixInfo(int x int y int rows int value) { X = x; Y = y; Rows = rows; Value = value; } public override string ToString() { return String.Format(At [{0} {1}] size {2} x {2} value {3} X Y Rows Value); } } class Program { static void Main() { int[] matrix = new int[] { {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 214 214 214 214} {222 222 222 222 222 222 222 222 222 222 222 214 214 214 214} {222 222 222 222 222 222 222 222 222 222 222 214 206 206 206} {222 222 222 222 222 222 222 222 222 222 222 206 206 206 206} {222 222 222 222 222 222 222 222 222 222 222 206 206 206 206} {222 222 222 222 222 222 222 222 222 222 222 214 214 214 214} }; List smiList = GenerateSubmatrices(matrix); int count = 0; foreach(SubmatrixInfo smi in smiList) { Console.WriteLine(smi); count++; if(count % 20 == 0) { Console.WriteLine(
Press any key to continue ...
); Console.ReadKey(); } } } static List GenerateSubmatrices(int[] matrix) { List smiList = new List (); int rows = matrix.GetLength(0); int cols = matrix.GetLength(1); int maxSize = (rows == cols) ? rows - 1 : Math.Min(rows cols); if (maxSize bool[] used = new bool[rows cols]; // all false initially int first = 0; bool isSame = false; for(int size = maxSize; size > 1; size--) { for(int x = 0; x { for(int y = 0; y { first = matrix[x y]; isSame = true; for(int sx = x; sx { for(int sy = y; sy { if (used[sx sy] || first != matrix[sx sy]) { isSame = false; goto next; } } } next: if (isSame) { smiList.Add(new SubmatrixInfo(x y  size  first)); for(int ux = x; ux { for(int uy = y; uy { used[ux uy] = true; } } } } } } return smiList; } }

aakash malhotra · Answer

Excellent work my friend. It is working fine. But the execution time is still a problem and it is a big problem since I am gonna work on 300*300 matrix. I was thinking that may be we can reduce time if we look for square matrices of order higher than 9*9 and we look for isolated square matrices for eg: 1 3 4 5 5 5 7 7 2 3 4 5 5 5 4 3 9 8 7 7 7 4 3 2 2 4 7 7 7 6 6 6 3 2 7 7 7 5 3 1 9 8 4 3 2 5 6 5 3 4 4 5 2 1 0 9 2 4 4 6 3 2 1 9 in the above matrix the 3*3 order matrix of 7's in the center is an isolated matrix since it stands apart not surrounded by any other 7 but the 2*2 matrix of 4's at bottom left is not an isolated square matrix since there is an extra 4 in the neighboring elements...  similarly the 2*2 matrix of 5's in top center is not an isolated square matrix due to the two extra neighboring 5's So we can just find all the isolated square matrices of order 9*9 and above....

Alan · Answer

OK I've come up with a solution which deals with this problem for the 15 x 15 matrix but I'm not sure whether it solves it completely or not. The idea is to have two passes to remove the intersections. The first pass only removes those matrices which intersect on both sides of the sort order and the second pass removes the remaining intersections. The full code is reproduced for convenience: using System; using System.Collections.Generic; // Information for same value square submatrix struct SubmatrixInfo : IComparable IEquatable { public static int ParentRows; // number of rows in parent matrix public readonly int X; // x coordinate in parent of top left element public readonly int Y; // y coordinate in parent of top left element public readonly int Rows; // number of rows and hence columns in submatrix public readonly int Value; // common value of elements public SubmatrixInfo(int x int y int rows int value) { X = x; Y = y; Rows = rows; Value = value; } public long Key { get{ return ParentRows * ParentRows * Rows + ParentRows * (ParentRows - X) + ParentRows - Y;} } public int CompareTo(object smi) { SubmatrixInfo other = (SubmatrixInfo)smi; return Math.Sign(other.Key - this.Key); } public override string ToString() { return String.Format(At [{0} {1}] size {2} x {2} value {3} X Y Rows Value); } public bool Equals(SubmatrixInfo other) { if (this.Key == other.Key) return true; return false; } public bool IsSubmatrixOf(SubmatrixInfo other) { if (this.Rows >= other.Rows) return false; if ((other.X (other.Y return false; } public bool IntersectsWith(SubmatrixInfo other) { return (other.X } } class Program { static void Main() { int[] matrix = new int[] { {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 214 214 214 214} {222 222 222 222 222 222 222 222 222 222 222 214 214 214 214} {222 222 222 222 222 222 222 222 222 222 222 214 206 206 206} {222 222 222 222 222 222 222 222 222 222 222 206 206 206 206} {222 222 222 222 222 222 222 222 222 222 222 206 206 206 206} {222 222 222 222 222 222 222 222 222 222 222 214 214 214 214} }; List smiList = GenerateSubmatrices(matrix); int count = 0; foreach(SubmatrixInfo smi in smiList) { Console.WriteLine(smi); count++; if(count % 20 == 0) { Console.WriteLine(
Press any key to continue ...
); Console.ReadKey(); } } } static List GenerateSubmatrices(int[] matrix) { int n = matrix.GetLength(0); if (n (); SubmatrixInfo.ParentRows = n; List smiList = GetSubmatrices(matrix 0 0); smiList.Sort(); if (smiList.Count == 1) return smiList; // remove submatrices which are submatrices of others in list for (int i = smiList.Count - 1; i > 0; i--) { for (int j = i - 1; j >= 0; j--) { if (smiList[i].IsSubmatrixOf(smiList[j])) { smiList.RemoveAt(i); break; } } } // remove submatrices which intersect with others in list // first remove those that intersect on both sides for (int i = smiList.Count - 2; i > 0; i--) { for (int j = i - 1; j >= 0; j--) { if (smiList[i].IntersectsWith(smiList[j]) && smiList[i].IntersectsWith(smiList[i + 1])) { smiList.RemoveAt(i); break; } } } // now remove any remaining intersections for (int i = smiList.Count - 1; i > 0; i--) { for (int j = i - 1; j >= 0; j--) { if (smiList[i].IntersectsWith(smiList[j])) { smiList.RemoveAt(i); break; } } } return smiList; } static List GetSubmatrices(int[] matrix int absX int absY) { List smiList = new List (); int n = matrix.GetLength(0); if (n for (int z = 0; z { int startX = 0 endX = n - 2 startY = 0 endY = n - 2; switch(z) { case 0 : // top left break; case 1 : // top right startX = 1; endX = n - 1; startY = 0; endY = n - 2; break; case 2 : // bottom left startX = 0; endX = n - 2; startY = 1; endY = n - 1; break; case 3 : // bottom right startX = startY = 1; endX = endY = n - 1; break; } int[] submatrix = new int[n - 1 n - 1]; int first = matrix[startX startY]; int next = first; bool isSame = true; for (int x = startX; x { for (int y = startY; y { next = matrix[x y]; if (isSame && next != first) { isSame = false; } submatrix[x - startX y - startY] = next; } } if (isSame) { SubmatrixInfo smi = new SubmatrixInfo(absX + startX absY +startY n - 1 first); if(!smiList.Contains(smi)) smiList.Add(smi); } else if (n > 2) { List temp = GetSubmatrices(submatrix absX + startX absY + startY); foreach(SubmatrixInfo smi in temp) { if (!smiList.Contains(smi)) smiList.Add(smi); } } } return smiList; } }

Alan · Answer

I've just tried the new version with the 15 x 15 matrix: int[] matrix = new int[] { {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 222 222 222 222} {222 222 222 222 222 222 222 222 222 222 222 214 214 214 214} {222 222 222 222 222 222 222 222 222 222 222 214 214 214 214} {222 222 222 222 222 222 222 222 222 222 222 214 206 206 206} {222 222 222 222 222 222 222 222 222 222 222 206 206 206 206} {222 222 222 222 222 222 222 222 222 222 222 206 206 206 206} {222 222 222 222 222 222 222 222 222 222 222 214 214 214 214} }; and there's a problem which I hadn't anticipated with the three intersecting 2 x 2 matrices starting at [911] [912] and [913]. Unfortunately working backwards the last one is eliminated because it intersects with the last but one and then that one is eliminated because it intersects with the other one! We doof course want the two disjoint matrices [911] and [913] to be returned here. I can't immediately see how to deal with this but I'm working on it :) Incidentally I think there should be just four results here (not 8) : the 11 x 11 the 3 x 3 and the two 2 x 2 matrices.

Alan · Answer

OK I've fixed it to exclude submatrices which intersect with bigger submatrices or with submatrices of the same size but earlier in the sorting order. Can't do anything about the speed though as the trouble with the algorithm is that there's a lot of redundant operations :( using System; using System.Collections.Generic; // Information for same value square submatrix struct SubmatrixInfo : IComparable IEquatable { public static int ParentRows; // number of rows in parent matrix public readonly int X; // x coordinate in parent of top left element public readonly int Y; // y coordinate in parent of top left element public readonly int Rows; // number of rows and hence columns in submatrix public readonly int Value; // common value of elements public SubmatrixInfo(int x int y int rows int value) { X = x; Y = y; Rows = rows; Value = value; } public long Key { get{ return ParentRows * ParentRows * Rows + ParentRows * (ParentRows - X) + ParentRows - Y;} } public int CompareTo(object smi) { SubmatrixInfo other = (SubmatrixInfo)smi; return Math.Sign(other.Key - this.Key); } public override string ToString() { return String.Format(At [{0} {1}] size {2} x {2} value {3} X Y Rows Value); } public bool Equals(SubmatrixInfo other) { if (this.Key == other.Key) return true; return false; } public bool IsSubmatrixOf(SubmatrixInfo other) { if (this.Rows >= other.Rows) return false; if ((other.X (other.Y return false; } public bool IntersectsWith(SubmatrixInfo other) { return (other.X } } class Program { static void Main() { int[] matrix = new int[] { {1 4 5 6 7 8 5 3 4} {3 7 7 9 4 2 2 2 5} {8 7 7 8 5 3 2 2 1} {6 6 7 8 6 3 1 2 3} {6 6 8 3 1 1 4 9 0} {3 3 3 6 1 1 2 2 0} {3 3 3 4 5 6 0 9 1} {3 3 3 4 5 6 2 1 0} {3 3 3 4 5 6 7 8 9} }; List smiList = GenerateSubmatrices(matrix); int count = 0; foreach(SubmatrixInfo smi in smiList) { Console.WriteLine(smi); count++; if(count % 20 == 0) { Console.WriteLine(
Press any key to continue ...
); Console.ReadKey(); } } } static List GenerateSubmatrices(int[] matrix) { int n = matrix.GetLength(0); if (n (); SubmatrixInfo.ParentRows = n; List smiList = GetSubmatrices(matrix 0 0); smiList.Sort(); if (smiList.Count == 1) return smiList; // remove submatrices which are submatrices of others in list for (int i = smiList.Count - 1; i > 0; i--) { for (int j = i - 1; j >= 0; j--) { if (smiList[i].IsSubmatrixOf(smiList[j])) { smiList.RemoveAt(i); break; } } } // remove submatrices which intersect with others in list for (int i = smiList.Count - 1; i > 0; i--) { for (int j = i - 1; j >= 0; j--) { if (smiList[i].IntersectsWith(smiList[j])) { smiList.RemoveAt(i); break; } } } return smiList; } static List GetSubmatrices(int[] matrix int absX int absY) { List smiList = new List (); int n = matrix.GetLength(0); if (n for (int z = 0; z { int startX = 0 endX = n - 2 startY = 0 endY = n - 2; switch(z) { case 0 : // top left break; case 1 : // top right startX = 1; endX = n - 1; startY = 0; endY = n - 2; break; case 2 : // bottom left startX = 0; endX = n - 2; startY = 1; endY = n - 1; break; case 3 : // bottom right startX = startY = 1; endX = endY = n - 1; break; } int[] submatrix = new int[n - 1 n - 1]; int first = matrix[startX startY]; int next = first; bool isSame = true; for (int x = startX; x { for (int y = startY; y { next = matrix[x y]; if (isSame && next != first) { isSame = false; } submatrix[x - startX y - startY] = next; } } if (isSame) { SubmatrixInfo smi = new SubmatrixInfo(absX + startX absY +startY n - 1 first); if(!smiList.Contains(smi)) smiList.Add(smi); } else if (n > 2) { List temp = GetSubmatrices(submatrix absX + startX absY + startY); foreach(SubmatrixInfo smi in temp) { if (!smiList.Contains(smi)) smiList.Add(smi); } } } return smiList; } }

aakash malhotra · Answer

Hi : Thanks for the reply. Very helpful indeed but the prob is it takes ages to compute for a 300*300 matrix. There is some prob in the detection and i think you will be able to help. It doesnt detect unique sub matrices for eg. Consider this matrix 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 214 214 214 214 222 222 222 222 222 222 222 222 222 222 222 214 214 214 214 222 222 222 222 222 222 222 222 222 222 222 214 206 206 206 222 222 222 222 222 222 222 222 222 222 222 206 206 206 206 222 222 222 222 222 222 222 222 222 222 222 206 206 206 206 222 222 222 222 222 222 222 222 222 222 222 214 214 214 214 In this matrix the number of sub matrices with all elements having same value is 8 but your code detects it as 14. There is a submatrix of dimension 11*11 with all 222's. It should detect it a 11*11 sub matrix(largest) and proceed but it detects a 11*11 matrix of 222 5 times. This due to intersection of elements. Can we fix this. I ll appreciate your help. Thank you

Alan · Answer

This isn't an easy one to figure out but I've come up with the program below which seems to be working OK. The program uses a recursive algorithm to generate all possible sub-matrices whose elements have the same value. I've then sorted them so that the bigger matrices are displayed first and filtered them to exclude matrices which are themselves submatrices of other matrices in the list (for example the 3 x 3 matrix has four 2 x 2 submatrices with values of 3). However I haven't attempted to exclude matrices which simply intersect one another as it's not clear which one should be removed! Because of the algorithm used (which frankly isn't ideal) the program only works when the 'parent' matrix is itself square so I've had to add a further row to your example matrix to make it 9 x 9 (I also allowed for a 3 x 3 intersection here). However it should in theory work for your 300 x 300 matrix as long as the processing time is acceptable and the recursive calls don't overflow the stack. using System; using System.Collections.Generic; // Information for same value square submatrix struct SubmatrixInfo : IComparable IEquatable { public static int ParentRows; // number of rows in parent matrix public readonly int X; // x coordinate in parent of top left element public readonly int Y; // y coordinate in parent of top left element public readonly int Rows; // number of rows and hence columns in submatrix public readonly int Value; // common value of elements public SubmatrixInfo(int x int y int rows int value) { X = x; Y = y; Rows = rows; Value = value; } public long Key { get{ return ParentRows * ParentRows * Rows + ParentRows * (ParentRows - X) + ParentRows - Y;} } public int CompareTo(object smi) { SubmatrixInfo other = (SubmatrixInfo)smi; return Math.Sign(other.Key - this.Key); } public override string ToString() { return String.Format(At [{0} {1}] size {2} x {2} value {3} X Y Rows Value); } public bool Equals(SubmatrixInfo other) { if (this.Key == other.Key) return true; return false; } public bool IsSubmatrixOf(SubmatrixInfo other) { if (this.Rows >= other.Rows) return false; if ((other.X (other.Y return false; } } class Program { static void Main() { int[] matrix = new int[] { {1 4 5 6 7 8 5 3 4} {3 7 7 9 4 2 2 2 5} {8 7 7 8 5 3 2 2 1} {6 6 7 8 6 3 1 2 3} {6 6 8 3 1 1 4 9 0} {3 3 3 6 1 1 2 2 0} {3 3 3 4 5 6 0 9 1} {3 3 3 4 5 6 2 1 0} {3 3 3 4 5 6 7 8 9} }; List smiList = GenerateSubmatrices(matrix); int count = 0; foreach(SubmatrixInfo smi in smiList) { Console.WriteLine(smi); count++; if(count % 20 == 0) { Console.WriteLine(
Press any key to continue ...
); Console.ReadKey(); } } } static List GenerateSubmatrices(int[] matrix) { int n = matrix.GetLength(0); if (n (); SubmatrixInfo.ParentRows = n; List smiList = GetSubmatrices(matrix 0 0); smiList.Sort(); if (smiList.Count == 1) return smiList; // remove submatrices which are submatrices of others in list) for (int i = smiList.Count - 1; i > 0; i--) { for (int j = i - 1; j >= 0; j--) { if (smiList[i].IsSubmatrixOf(smiList[j])) { smiList.RemoveAt(i); break; } } } return smiList; } static List GetSubmatrices(int[] matrix int absX int absY) { List smiList = new List (); int n = matrix.GetLength(0); if (n for (int z = 0; z { int startX = 0 endX = n - 2 startY = 0 endY = n - 2; switch(z) { case 0 : // top left break; case 1 : // top right startX = 1; endX = n - 1; startY = 0; endY = n - 2; break; case 2 : // bottom left startX = 0; endX = n - 2; startY = 1; endY = n - 1; break; case 3 : // bottom right startX = startY = 1; endX = endY = n - 1; break; } int[] submatrix = new int[n - 1 n - 1]; int first = matrix[startX startY]; int next = first; bool isSame = true; for (int x = startX; x { for (int y = startY; y { next = matrix[x y]; if (isSame && next != first) { isSame = false; } submatrix[x - startX y - startY] = next; } } if (isSame) { SubmatrixInfo smi = new SubmatrixInfo(absX + startX absY +startY n - 1 first); if(!smiList.Contains(smi)) smiList.Add(smi); } else if (n > 2) { List temp = GetSubmatrices(submatrix absX + startX absY + startY); foreach(SubmatrixInfo smi in temp) { if (!smiList.Contains(smi)) smiList.Add(smi); } } } return smiList; } }