7

The best idea I have so far is to rotate first array by {0, 90, 180, 270} degrees and reflect it horizontally or/and vertically. We basically get 16 variations [1] of first array and compare them with second array. if none of them matches the two arrays are rotationally and reflectively distinct.

I am wondering if there is more optimal solution than this brute-force approach?

[1]

0deg, no reflection
0deg, reflect over x
0deg, reflect over y
0deg, reflect over x and y
90deg, no reflection
...
  • 2
    Note that reflection over x and y is the same as rotation by 180 degrees. This way you don't need to check for 180 or 270 degrees, reducing the number of options to check to 8. – Daan Wilmer Nov 11 '13 at 15:43
  • 2
    Column/Row based summation could be a quick easy heuristic to knock out a lot of your options so you only do a full equality compare when the sum of all columns/rows are identical on both sides. (Remember, the sum of columns becomes sum of rows on rotation and another rotation makes them columns again, reflection the sum stays the same) – Jimmy Hoffa Nov 11 '13 at 15:57
  • In my scenario I have boolean arrays and I am only comparing ones with same number of true/false elements, so checksums won't improve anything. -- so just confirming that its only composed of 1/0 or t/f rather than other values? – user40980 Nov 11 '13 at 17:19
1

Break this into two problems:

  1. How would you compare two square arrays - I'll call these matrices - that cannot be rotated or reflected, and
  2. How would you compare an item that can be rotated and reflect against another item

Implementing the first problem with a naive approach gives a very simple answer - walk the matrices in parallel, stopping once you find non-equal values. If you walk the entire matrix without non-equal values then the matrices are equal. To walk the matrix, loop through columns, inner loop through each row, and compare values. Note that walking the matrix allows us to enumerate over all items in the matrix as if they were a single linear collection.

For the second problem, there are eight different ways to rotate and reflect a matrix. There are four corners to be used as a starting point, and an algorithm can walk from each corner in two directions (i.e. horizontally or vertically). Thus we will need to perform 'problem 1' over each of the eight perspectives of the original matrix.

How would I implement this? We can walk the eight matrices in parallel or sequentially; I'll implement this sequentially as potentially faster (if the first matrix checked is a match, no other checks are required) but more importantly it will be simpler.

Each of the eight matrices to check should be represented by a walking function f(x) to retrieve the xth value. For instance, in an n by n square array A,

f1(x) = A[x % n, x / n]; // walking rows first, then columns
f2(x) = A[x / n, x % n]; // walking columns first, then rows

// using a different starting point
f3(x) = A[n - (x / n), x % n];
f4(x) = A[n - (x % n), x / n];

and so on. Now simply,

foreach walking function
    foreach value in walking function
        if value not equal to corresponding value in target 
            next walking function
    return true // not non-equal values found
return false // none of the functions matched
3

To devise an appropriate strategy, it is useful to know how the input is likely to be. For instance if you have large arrays full of zeroes containing a hand of ones, then computing the checksum will quickly lead you to negative answers, but if your arrays are full of random data, the checksum will not be that helpful, comparing the first coefficient will usually be enough to tell one array apart from the other.

I am wondering if there is more optimal solution than this brute-force approach?

For general input, there is no better solution. However, note that you can avoid to copy the array by defining a custom accessor, i.e. a function taking coordinates in the array and one of our 16 permutations as well as arguments, to access the checked array.

  • +1 optimal solution always depends on knowing the likely data. The optimal solution for unknown data is unlikely to be optimal for known data. – Kirk Broadhurst Nov 18 '13 at 15:58
2

You might consider calculating a checksum for an array and compare the checksums of two arrays.

Checksums are order-independent; if two arrays have different checksums, they definitely cannot have the same elements in a different (e.g. rotated) arrangement.

If you have to compare arrays many times, you can cache the sums and save on re-calculation.

  • 1
    Your square is divided into 8 triangles, and if some of them are equal, it might be that it is not rotationally distinct, for example. So, what you do is that you compute a hash for each of the 8 triangles (which means that you only need to iterate over the entire array once), and then do some comparison of the 8 hashes. If some of these hashes are equal, well, THEN you can compare the triangles, (and now not only the large array), so this is still effective. – Per Alexandersson Nov 11 '13 at 15:59
  • 1
    @JimmyHoffa: a checksum does require iteration over the entire triangle, and any other sane algorithm would. If checksums match, though, the odds of the squares being equal after some rotation is higher. If the sums don't match, the squares are different, in any rotation. So a checksum might spare you up to 4 direct comparisons and 3 rotations for the price of one comparison. – 9000 Nov 11 '13 at 16:29
  • @Paxinum: the triangles idea is nice; could you plz make a proper answer out of it? – 9000 Nov 11 '13 at 16:34
  • @9000 it's monday, I read "hash" not "checksum" my bad. – Jimmy Hoffa Nov 11 '13 at 16:38
  • In my scenario I have boolean arrays and I am only comparing ones with same number of true/false elements, so checksums won't improve anything. But generally it's a good idea. – Žan Kusterle Nov 11 '13 at 16:52
2

Divide your square into 8 smaller triangles. compute a hash/checksum on each of these triangles. This only requires one iteration over the entire square.

Now, in order for some symmetry to be present, some of these triangles must be equal, and thus their hash values. So, if all has values are different, you are done.

Otherwise, compare the triangles with the same hash values only. This saves you some time, but it is of course a bit trickier to implement.

  • If you define the hash function so that a mirrored triangle has the negative value, you can add the two triangles on either side of the diagonal. But the price is that the diagonals themselves do not count. Those are easily checked, though, and that's a worthy optimization in itself. (Only 4 possibilities for them instead of 8) – MSalters Nov 11 '13 at 17:54

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.