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 `X`

s and `V`

s.

```
> -- @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 `X`

s and how many `V`

s still need to be generated.

```
> where
> go 0 v = [replicate v 'V']
> go x 0 = [replicate x 'X']
```

If the number of `X`

s or `V`

s 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.

Pingback: Efficiently listing orthobraces | The Math Less Traveled