CODEWITHSUNDEEP
mathmatrixoptimizationsymmetry
Sniggerfardimungus
Sniggerfardimungus

Reputation: 11831

How can I detect all symmetries in a collection of large boolean arrays?

I have a project that involves an unbounded grid of booleans. The grid is very sparsely populated in that I doubt that there will ever be more than 8 Trues in the entire grid. I'm optimizing a brute force problem, where the starting layout of Trues is used as a seed for further work. I want to ensure that I never run the same search on a pair of symmetrically identical boards.

Rotation, translation, and mirroring are all irrelevant symmetries. This matrix:

A 0 0 0 0
0 0 0 B 0
0 C 0 0 0
0 0 0 0 0
0 0 0 0 0

should be considered identical to:

0 0 0 B 0 0
0 0 0 0 0 0
0 0 C 0 0 0
0 0 0 0 A 0
0 0 0 0 0 0 
0 0 0 0 0 0

A, B, and C are all "trues", but are labeled uniquely, here, so it's easier to see the transposition. The matrix has been mirrored, rotated, and translated. The matrices are logically infinite, but for the sake of symmetry elimination, they can be trimmed to the minimum dimensions that contain all the trues.

Whatever I end up using for this needs to be fast. Fortunately, the 8 trues in the matrix are likely to be confined to a 25x25 subsection of the space, so hopefully we can pull this off in a single pass.

I've contemplated finding the escribing rectangle, rotating and mirroring it so its dominant axis is horizontal and (any consistent set of requirements here), but it ends up being many passes in order to guarantee detection of all symmetries.

Upvotes: 1

Views: 51

Answers (0)

Related Questions