Email list hosting service & mailing list manager


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)))