Lets say you have a binary number with n amount of digits, 4 for example, I know I could get all the permutations by simply using the formula 2^n. This gives 16 unique combinations so I could simply take the numbers 1-16 and convert it to binary: {0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 0000}

1: How do I filter out mirror matches like (0001,1000) or (1010,0101) where the number is just flipped.

2: Similarly, cases where the number is just shifted left or right (0001,0010,0100,1000) or (0011,0110,1100).

3:Do the same as above on a grid of x,y size adding another dimension for example:
arrays represented as grid

In the first example the arrays can be represented as follows but they need to be filtered out as they are the same "object". The second example shows a similar case but the "object" is not actually attached to itself.

example 1:

original: {0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1}
x-1,y-1: {0,1,0,0,0,1,0,0,0,1,1,0,0,0,0,0}
flipped y axis: {0,0,1,1,0,0,1,0,0,0,1,0,0,0,0,0}
flipped x axis: {0,0,0,0,0,1,0,0,0,1,0,0,1,1,0,0}

example 2

original: {0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0}
x-1,y-1: {1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0}
flipped y axis: {0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0}
flipped x axis: {0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0}

  • $\begingroup$ What have you tried so far? Have you tried calculating the number of mirror matches for a given $n$? $\endgroup$
    – Ryan
    Aug 11, 2020 at 23:20
  • $\begingroup$ I've checked for n=4 i.imgur.com/cCgiyyn.png Couldn't really see a pattern between them, I originally thought the first half of the binary data would just be mirrored in the second half but that's completely wrong. There isn't even a pattern between offset of pairs from what I see either. There are 6 pairs out of the 16 possible and 4 unique ones so 6 can be filtered out. For now I'm just trying to find the mirror matches, not sure how to tackle the translation ones without a brute force algorithm. $\endgroup$ Aug 11, 2020 at 23:45
  • $\begingroup$ How complicated of an answer do you want? If you want to consider all of these simultaneously, I'd recommend burnside's lemma or polya's enumeration theorem, but given the way you've phrased this I'm not sure you'll have all the background. $\endgroup$
    – JMoravitz
    Aug 11, 2020 at 23:51
  • $\begingroup$ @CalculatedRisk Are you sure there are $6$ mirror matches for $n=4$? I believe the only ones in this case are $0000,\:0110,\:1001,\: 1111 $ $\endgroup$
    – Ryan
    Aug 11, 2020 at 23:53
  • $\begingroup$ @Ryan In the case of mirror matching something like 1000 and 0001 are effectively the same for my purposes, I should've clarified that better. $\endgroup$ Aug 11, 2020 at 23:56


Your Answer

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

Browse other questions tagged or ask your own question.