How to remove duplicated matrix (represented in array)?
This title is not fully depicted what I mean, but I just can't come up with a better one. Let me just describe my problem.
I have an array with many arrays as its elements. It looks like
[
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p],
[i, j, k, l, m, n, o, p, a, b, c, d, e, f, g, h],
[m, i, e, a, n, j, f, b, o, k, g, c, p, l, h, d],
...
]
In fact, every element represents an matrix, so you can understand the upper array as
[
+- -+
| a, b, c, d |
| e, f, g, h |
| i, j, k, l | // matrix1
| m, n, o, p |
+- -+ ,
+- -+
| i, j, k, l |
| m, n, o, p |
| a, b, c, d |
| e, f, g, h |
+- -+ ,
+- -+
| m, i, e, a |
| n, j, f, b | // matrix2
| o, k开发者_JAVA技巧, g, c |
| p, l, h, d |
+- -+ ,
...
]
My array is the super set of all matrix that make up of letters from a to p. Some matrix in the array are considered duplicated. If you flip a matrix horizontally, vertically, by the two diagonals, or rotate it 90, 180, 270 degrees and the result matrix is included in my array, then these two matrix are considered "duplicate". For example, if you rotate matrix1 90 degrees clockwise, you will get matrix2. So matrix2 and matrix1 are considered duplicated. We just need one of them. My question is, what's the best (easiest) way to remove the duplicates in my original array (which one is removed and which one is retained is not an issue, you just retain one of them )?
Thanks.
I suggest that you define some "standard" way of representing your matrices. The representation should have the property that matrices that are rotations and mirrors of each other have the same representation, and that all matrices that are not rotationss and mirrors of each other have different representations. Since all letters in a matrix are unique in your case, you could define the "standard" representation as follows: given a matrix, rotate and flip it so that the lowest letter among all corner letters ends up in the top left corner, and the second lowest letter (among the two corners that are adjacent to the one with the smallest letter) ends up in the top right corner. Then, "compress" the matrix into a string. For instance, both
h b d j
l n f i
o g a k
n c p e
and
e k i j
p a f d
c g n b
n o l h
(which is the first matrix rotated 90 degrees clockwise and then flipped upside down) would have the standard representation ekijpafdcgnbnolh
. You can now iterate through all your matrices, generate the standard representation for each and put it into a HashSet
if it is not there already. Discard all matrices whose standard representation is already present in the set.
精彩评论