Let’s see some simple Haskell code to generate orthobraces, by generating all sequences and throwing away ones we’ve already generated.
First, some library imports we’ll need.
> import Data.List > import qualified Data.Set as S
Here’s a function to generate all sequences with
> -- @orthoseqs n@ generates all length 2n+4 *sequences* with n+4 X's and > -- n V's. > orthoseqs :: Int -> [[Char]] > orthoseqs n = go (n+4) n
orthoseqs works by calling a recursive helper function
go, which keeps track of how many
Xs and how many
Vs still need to be generated.
> where > go 0 v = [replicate v 'V'] > go x 0 = [replicate x 'X']
If the number of
Vs remaining is , we just output the right number of copies of the other letter.
> go x v = map ('X':) (go (x-1) v) ++ map ('V':) (go x (v-1))
Otherwise, we recursively generate all strings with
V’s, and put an
X on the front of each; and similarly for strings with a
V at the beginning.
Let’s try it:
ghci> orthoseqs 0 ["XXXX"] ghci> orthoseqs 1 ["XXXXXV","XXXXVX","XXXVXX","XXVXXX","XVXXXX","VXXXXX"] ghci> length (orthoseqs 2) 28 ghci> length (orthoseqs 3) 120
This looks right and seems to match up with the numbers we computed last time.
Now, to throw out sequences which are equivalent up to rotation and/or reversal, the easiest way is to write a function
canonicalize which computes a canonical representative from each equivalence class: in particular, given a sequence, it computes the lexicographically smallest (that’s a fancy way of saying “comes first in dictionary order”) sequence which is equivalent to it.
> canonicalize :: Ord a => [a] -> [a] > canonicalize as = minimum (rots as ++ rots (reverse as))
canonicalize just finds the minimum sequence among all rotations of
as and rotations of
> where > rots xs = map (take n) . take n . tails $ xs ++ xs > where > n = length xs
To generate all rotations, we do a little list manipulation:
xs ++ xs puts two copies of
xs together end to end;
tails produces something like this:
ghci> xs = [1,4,5] ghci> tails (xs ++ xs) [[1,4,5,1,4,5],[4,5,1,4,5],[5,1,4,5],[1,4,5],[4,5],,]
Then we take just the first results of
tails and take only the first
n elements of each, like so:
ghci> map (take 3) . take 3 . tails $ xs ++ xs [[1,4,5],[4,5,1],[5,1,4]]
Now we can write
orthobraces fairly simply: generate all sequences, canonicalize each (resulting in a bunch of duplicates), then put them into a set (which gets rid of duplicates) and list the elements of the set.
> -- @orthobraces n@ generates all length 2n+4 *bracelets* with n+4 X's > -- and n V's. That is, one representative is generated for each > -- bracelet, up to reflection and rotation. > orthobraces :: Int -> [[Char]] > orthobraces = S.toList . S.fromList . map canonicalize . orthoseqs
Let’s try it:
ghci> orthobraces 0 ["XXXX"] ghci> orthobraces 1 ["VXXXXX"] ghci> orthobraces 2 ["VVXXXXXX","VXVXXXXX","VXXVXXXX","VXXXVXXX"] ghci> orthobraces 3 ["VVVXXXXXXX","VVXVXXXXXX","VVXXVXXXXX","VVXXXVXXXX","VXVXVXXXXX","VXVXXVXXXX","VXVXXXVXXX","VXXVXXVXXX"] ghci> map (length . orthobraces) [0..6] [1,1,4,8,29,79,280]
It seems to work! As we already discussed last time, this is not a particularly efficient way to generate orthobraces, since we end up spending most of our time throwing away duplicates (and what’s worse, even the proportion of time spent throwing away duplicates increases as increases). But it’s rather simple to write and test, and can serve as a good reference implementation to compare other implementations against.
Pingback: Efficiently listing orthobraces | The Math Less Traveled