Arrays, rotations, beer coasters, and symmetries of a hypercube
Bradley Lucier 04 May 2023 22:57 UTC
TL;DR: You can generate every "symmetry" of an array by combining one
permutation and one reversal.
I defined a little array with a big F in the middle:
(define A
(list*->array 2 '((_ F F F _)
(_ F _ _ _)
(_ F F F _)
(_ F _ _ _)
(_ F _ _ _))))
and thought about the nontrivial permutations and reversals of A (using
array->list* and Gambit's pretty-print):
(array-permute A '#(1 0))
((_ _ _ _ _)
(F F F F F)
(F _ F _ _)
(F _ F _ _)
(_ _ _ _ _))
(array-reverse A '#(#f #t))
((_ F F F _)
(_ _ _ F _)
(_ F F F _)
(_ _ _ F _)
(_ _ _ F _))
(array-reverse A '#(#t #f))
((_ F _ _ _)
(_ F _ _ _)
(_ F F F _)
(_ F _ _ _)
(_ F F F _))
(array-reverse A '#(#t #t))
((_ _ _ F _)
(_ _ _ F _)
(_ F F F _)
(_ _ _ F _)
(_ F F F _))
All but the last have the big F pointing the wrong way, like the array
was a coaster under a drink and it's been flipped over. The last one
has rotated the original array by 180 degrees, *without* flipping over
the coaster.
I wondered whether you could combine a permutation and a reversal to get
a counterclockwise rotation by 90 degrees, and it's easy to see that
(array-reverse (array-permute A '#(1 0)) '#(#t #f))
((_ _ _ _ _)
(F _ F _ _)
(F _ F _ _)
(F F F F F)
(_ _ _ _ _))
So I generated all combinations of array-permute and array-reverse (even
the trivial ones that don't modify the array):
(array-reverse (array-permute A '#(0 1)) '#(#f #f))
((_ F F F _)
(_ F _ _ _)
(_ F F F _)
(_ F _ _ _)
(_ F _ _ _))
(array-reverse (array-permute A '#(0 1)) '#(#f #t))
((_ F F F _)
(_ _ _ F _)
(_ F F F _)
(_ _ _ F _)
(_ _ _ F _))
(array-reverse (array-permute A '#(0 1)) '#(#t #f))
((_ F _ _ _)
(_ F _ _ _)
(_ F F F _)
(_ F _ _ _)
(_ F F F _))
(array-reverse (array-permute A '#(0 1)) '#(#t #t))
((_ _ _ F _)
(_ _ _ F _)
(_ F F F _)
(_ _ _ F _)
(_ F F F _))
(array-reverse (array-permute A '#(1 0)) '#(#f #f))
((_ _ _ _ _)
(F F F F F)
(F _ F _ _)
(F _ F _ _)
(_ _ _ _ _))
(array-reverse (array-permute A '#(1 0)) '#(#f #t))
((_ _ _ _ _)
(F F F F F)
(_ _ F _ F)
(_ _ F _ F)
(_ _ _ _ _))
(array-reverse (array-permute A '#(1 0)) '#(#t #f))
((_ _ _ _ _)
(F _ F _ _)
(F _ F _ _)
(F F F F F)
(_ _ _ _ _))
(array-reverse (array-permute A '#(1 0)) '#(#t #t))
((_ _ _ _ _)
(_ _ F _ F)
(_ _ F _ F)
(F F F F F)
(_ _ _ _ _))
These 8 combinations give all orientations of the coaster: The four
rotations without flipping it over, and then the four rotations after
flipping it over.
In fact, combining array-reverse and array-permute is sufficient to
generate all $d!\times 2^d$ symmetries of a $d$-dimensional array:
https://en.wikipedia.org/wiki/Hyperoctahedral_group
And it's been nearly 50 years since I studied undergraduate group
theory, so no, I don't understand the Wikipedia page either.
Still. it's easy to see that combining array-permute and array-reverse
generates the correct number of distinct arrays:
There are $d!$ permutations, and they're all unique. And after each
permutation, one can choose to reverse (or not) each of the $d$ axes, so
that gives $2^d$ combinations of reversals for each permutation, and
*they're* all unique. So overall we have $d!\times 2^d$ unique
symmetries, which is all of them.
One can ask whether separating permutations from reversals is a good
design in this SRFI. I think it is, often one wants to do one without
the other, and it takes just two calls to get a general transform.
Code is at the end.
Brad
(import (srfi 231))
(define A
(list*->array 2 '((_ F F F _)
(_ F _ _ _)
(_ F F F _)
(_ F _ _ _)
(_ F _ _ _))))
(pretty-print '(array-permute A '#(1 0)))
(pretty-print (array->list*
(array-permute A '#(1 0))))
(for-each (lambda (flip?)
(pretty-print
`(array-reverse A ',flip?))
(pretty-print
(array->list*
(array-reverse A flip?))))
'(#(#f #t)
#(#t #f)
#(#t #t)))
(for-each (lambda (permutation)
(for-each (lambda (flip?)
(pretty-print
`(array-reverse
(array-permute A ',permutation)
',flip?))
(pretty-print
(array->list*
(array-reverse
(array-permute A permutation)
flip?))))
'(#(#f #f)
#(#f #t)
#(#t #f)
#(#t #t))))
'(#(0 1)
#(1 0)))