2
$\begingroup$

**

Read the bold text if you want a tl:dr

**

In a 2x2 grid where each node can be toogled on or off you can get the total amount of combinations by using the formula 2^n, n = x*y so 2^4 or 16 unique configurations.

{0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 0000}

If I take these numbers and plot them on a grid, we will see all 16 combinations in each of the green squares in this image. The green number representing the decimal equivalent of its binary
The red number represents the unique pairs that can be converted into each other by either rotational or mirror symmetry

Using Burnside's lemma, it states that there are (2^2 + 2^2 + 2^3 + 2^3 + 2^4 + 2^1 + 2^2 + 2^1)/8 = 6 unique combinations if you are counting rotations/flips/translations as repeats of the same object.

From what I understand, that is all Burnside's lemma is able to tell us. It does not provide a way to calculate those groupings and ignore objects that are repeated by rotational or mirror symmetry.

In the case of n=4 I am looking for a mathematical formula to output 1,3,6,7,15, and of course 0 as every other configuration can be created by either rotating or flipping one of these around. I believe it is a given that the two extremities(all filled and all blank or (0,0,0,0) and (1,1,1,1)) are always going to be asymmetrical and in a group of their own irregardless of grid size. So in the case of a 3*3 grid or 2^9 we can instantly rule out (0,0,0,0,0,0,0,0,0) and 511 or (1,1,1,1,1,1,1,1,1) as asymmetrical and considered "unique objects". Following that logic n=4 should output 1,3,6,and 7 or all the numbers separated into these four remaining groups.


tl:dr

after writing everything out I think the easiest way to describe what I'm trying to do is like a monochrome bitmap reverse image detector. Instead of detecting defined images it catalogs every possible combination of squares on a grid of x,y size and groups them by "unique objects" see attached image

  • In a 2x2 grid there are 16 unique possibilities (2^4)
  • Of these 16, 6 of them are considered "seed nodes", this means that every possibility can be made by either rotating or flipping one of these nodes along an axis according to Burnside's lemma.
  • The six seed nodes in this case are 1,3,6,7,15, and 0 (the seed nodes could also arbitrarily be 4,5,9,13,15, and 0 just as long as it contains one from each group)
    for example Group 1 contains 4 numbers (1,2,4,8), and when represented in binary and plotted on the grids, you can cycle between all four configurations by continually doing 90 degree rotations
  • ------My Actual Questions------
  • 1:I think Burnside's lemma only considers rotational and mirror symmetry around the center point but it does not handle simple translations across the x and y axis or localized rotation. So what do I use instead?
  • 2: In a grid of a given size , Burnside's lemma tells me how many truly unique configurations are possible but how do I actually compute what they all are?
  • 3: How do I generate one of each such unique shape? I do not actually want to iterate through them all with a brute force algorithm and compare each shape to the rest. This quickly becomes impractical as the grid size increases.

      decimal value     |     grid 1  |  grid 2  |  grid 3  |  grid 4  |

Group 1:(1,2,4,8) = (0,0,0,1), (0,0,1,0), (0,1,0,0), (1,0,0,0)
Group 2:(3,5,10,12) = (0,0,1,1), (0,1,0,1), (1,0,1,0), (1,1,0,0)
Group 3:(6,9) = (0,1,1,0), (1,0,0,1)
Group 4:(7,11,13,14) = (0,1,1,1), (1,0,1,1), (1,1,0,1), (1,1,1,0)
Group 5:(15) = (1,1,1,1)
Group 6:(0) = (0,0,0,0)
*group 5 and group 6(all filled or all empty) aren't technically seeds because they will never have symmetry with any node besides itself, probably safe to remove from calculations?

In a 3x3 grid there will be 512 combinations and 102 unique groups to put them in. 100 if you dont count the fully filled and completely empty ones.

$\endgroup$

1 Answer 1

1
$\begingroup$

1: I think Burnside's lemma only considers rotational and mirror symmetry around the center point but it does not handle simple translations across the x and y axis or localized rotation. So what do I use instead?

This is correct, in so far as Burnside only considers the effect of a group of symmetries, where a group is a specific mathematical structure. In your case the translations do not form a group since you cannot translate the shape past the edge of the board. If your grid had wrap-around edges, then you could use Burnside to count the number of shapes if you wanted to.

I do not think that there is a easy direct way to count the number of unique shapes, but maybe it could be done using the inclusion-exclusion principle. That would deal with the translation (you exclude those shapes that fit on a smaller grid so you don't over-count them) but taking rotations/reflections into account too would be tricky.

2: In a grid of a given size , Burnside's lemma tells me how many truly unique configurations are possible but how do I actually compute what they all are?
3: How do I generate one of each such unique shape? I do not actually want to iterate through them all with a brute force algorithm and compare each shape to the rest. This quickly becomes impractical as the grid size increases.

I have to question why you want to pre-compute all possible "seed shapes". Even those will quickly become too numerous. For example the number of polyominoes with 15 cells is already over 3 million, so it very quickly gets worse if you allow disconnected shapes, too.

I reckon that all you need is a good way to convert any given image into a unique representative for that shape (i.e. "seed shape"). Your program can then store these representatives as it encounters them, and so be able to tell if it has already seen a shape before.

One way to create the unique representative is to rotate/mirror the given shape in all eight possible ways, translate those eight as far as possible towards the top-left corner of the grid, and then select whichever one of them is represented by the smallest binary number.

$\endgroup$
6
  • $\begingroup$ I haven't heard of the inclusion-exclusion principle but it kinda sounds similar to the method I was thinking of. If we take the existing seed nodes on the 2x2 grid and make sure the top left is filled in then we add new nodes to expand the grid on the bottom and the right and fill at least one of those nodes, translation would no longer be possible as the object is too large to move in the grid. Is that what that principle is? i.imgur.com/auJgguw.png Also, I have this idea but I doubt its this simple and it still relies on rotation and symmetry. $\endgroup$ Aug 13, 2020 at 19:04
  • $\begingroup$ So we discovered Burnside's lemma which can tell me there are 102 unique symmetry groups in a 3x3 grid but nobody has come up with an algorithm to solve those groups or better yet get one case for each group without iterating through all possibilities? Surely there's an algorithm to solve them if we can tell how many there are. $\endgroup$ Aug 13, 2020 at 19:07
  • $\begingroup$ What I'm actually trying to do is generate every unique shape possible in say a 5x5 grid in "the game of life" by John Conway. bitstorm.org/gameoflife Heres a link to it. I've already created a clone of the game and I want to create every possible shape and run a simulation for it. Given that there are 33 million configurations and most of them are repeats, I need some selective way of not generating the same object in different orientations. $\endgroup$ Aug 13, 2020 at 19:08
  • $\begingroup$ @CalculatedRisk 33 million is not very much and easily doable. Just loop through all possible patterns, for each generate a unique representative like I described, and only run simulations on those patterns that are exactly equal to their own representative. That way you don't even need to store a list of representatives you've already done. $\endgroup$ Aug 13, 2020 at 19:44
  • $\begingroup$ Yeah but Ideally, I was gonna classify all objects on a 100x100 grid and probably simulate a third dimension as color or something $\endgroup$ Aug 13, 2020 at 20:08

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.