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 Xs and Vs.

> -- @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 Xs or 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 X’s and 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 reverse as.

>   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],[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.