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