### Palindromic sequences in Clojure

Apr 13, 2015

Lately I’ve been obsessed with palindromes. I have no idea why, but I find the topic fascinating. Besides reading papers and books1 on the subject, I’ve been exploring writing some utilities for detecting2 and generating palindromes in Clojure sequences.

Before I talk about a couple of (IMO) cool Clojure functions, let me take a moment to define palindromic sequences. Simply put, a palindromic sequence is one that “reads” the same forwards and backwards, or in code has the following property:

```(= a-sequence (reverse a-sequence))
;;=> true
```

A concrete example of a palindromic sequence is the vector `[:a :b :b :a]`.

What led me to writing the functions below is that I’ve been toying around with a few game designs in my head that center around palindromes. Specifically, I’m writing an AI that can play these designs and flesh out some of the sticking points.3 However, to make the AI somewhat smart it has to be able to look at a group of things and determine all of the possible palindromes that can be built from it.

## Detecting

The first matter to deal with for my AI was to create a function that, given a sequence, returns `true` or `false` depending on whether it’s palindromic. I started out writing a convoluted `palindrome?` function that walked both ends of a sequence and compared the elements in place, but it wasn’t terribly efficient nor legible. Instead, I decided to just write the function almost exactly as I described it above:

```(defn palindrome? [s]
(= (seq s) (reverse s)))

(palindrome? [1 2 3 2 1])
;;=> true

(palindrome? [1 2 3 1 2])
;; false

(palindrome? "abba")
;;=> true
```

This turns out to be fairly fast, at least for my purposes, and it was definitely faster than my original. A nice property about this implementation is that it’ll detect palindromic strings4 also. This was a nice discovery, but the real fun came next.

## Finding palindromes

Given a Clojure vector of `[:a :b :b]` there are two possible palindromes that can be made from it: `[:b :b]` and `[:b :a :b]`. The way to find this answer is to perform the following steps:

1. Find all of the different ways to group the elements of the original
2. Calculate all of the different ways to arrange all of the groupings
3. Keep only the palindromes

Thankfully, for me there is a Clojure contrib library called math.combinatorics that has two functions, `partitions` and `permutations`, that could take care of #1 and #2. Unfortunately for me, math.combinatorics only handles sequences of numbers, so I had to use modified versions5 of the functions `parts` and `perms` instead.

First, to find all of the groupings of the original I just need to calculate the possible partitions:

```(->> (comb/parts [:a :b :b])) ;; calc groupings

;;=> (([:a :b :b])
;;    ([:a :b] [:b])
;;    ([:a] [:b :b])
;;    ([:a] [:b] [:b]))
```

You’ll notice that this doesn’t create separate groups for the groups of `:a` and the first `:b` and another for the second `:b`. This is because the groups created are considered equivalent and not replicated. However, using a different input set shows a different behavior:

```(->> (comb/parts [:a :b :c])) ;; calc groupings

;;=> (([:a :b :c])
;;    ([:a :b] [:c])
;;    ([:a :c] [:b])
;;    ([:a] [:b :c])
;;    ([:a] [:b] [:c]))
```

So you see, `[:a :b]` and `[:a :c]` are both generated. Without going too far afield, using my modified functions allows me to manipulate the way that groups are formed by overriding the `Comparable#compareTo` method, but that’s a different discussion.6

Now that I’ve calculated the groupings, I can gather them up and get rid of all of the duplicates and singleton groups (which are uninteresting palindromes indeed):

```(->> (comb/parts [:a :b :b])   ;; calc groupings
(apply concat)            ;; gather them up
(filter #(> (count %) 1)) ;; remove singletons
set)                      ;; remove dups

;;=> #{[:a :b] [:b :b] [:a :b :b]}
```

There are more efficient ways to get this result, but this is good enough for my purposes.

Now that I have the unique groupings I want to use `perms` to generate all of the possible arrangements of the groupings:

```(->> (comb/parts [:a :b :b])   ;; calc groupings
(apply concat)            ;; gather them up
(filter #(> (count %) 1)) ;; remove singletons
set                       ;; remove dups
(map comb/perms))         ;; calc arrangements

;;=> (([:a :b] [:b :a])
;;    ([:b :b])
;;    ([:a :b :b] [:b :a :b] [:b :b :a]))
```

So once again, I then want to gather the arrangements up and keep only the palindromes:

```(->> (comb/parts [:a :b :b])   ;; calc groupings
(apply concat)            ;; gather them up
(filter #(> (count %) 1)) ;; remove singletons
set                       ;; remove dups
(map comb/perms)          ;; calc arrangements
(apply concat)            ;; gather them up
(filter palindrome?))     ;; keep palindromes

;;=> ([:b :b] [:b :a :b])
```

And that’s it — all of the possible palindromes for `[:a :b :b]`.

## Done?

Even though there is a larger context to all of this, I wanted to share a few of the bits that I thought were interesting. There’s more to palindromic functions than what’s shown in this post, including a function to take a sequence and calculate the most “profitable” arrangement. For the purposes of the function, “profit” is defined as the total number of elements forming a palindrome (including sub-palindromes) in a sequence. For example, for the sequence `[:a :a :b :b]` the most profitable arrangement is `[:a :b :b :a]` worth 6 points (`[:a :b :b :a]` plus `[:b :b]`). That was fun to figure out, but I leave the implementation as an exercise to the reader.

Thanks for reading, and remember — never a foot too far, even.7

:F

1. Three wonderful books on the subject include Palindromes and Anagrams, Poetical Ingenuities and Eccentricities, and Go Hang a Salami! I’m a Lasagna Hog!

2. One of my favorite sites Programming Praxis recently had an entry on detecting palindromes. Even if you’re not interested in palindromes, PP is worth exploring.

3. During the implementation of this AI an interesting library (that I’m calling spielespielen) has fallen out. I might open it up one day, but the mix of functions is so bizarre that I find it hard to imagine that anyone but myself would find it useful. Still, it might make a good code painting

4. It detects pure palindromes only and not those that require a manipulation of punctuation and spacing.

5. I hope to submit a patch supporting the same in math.combinatorics soon, but if it’s not accepted then I’ll just use my own.

6. For the purposes of the game experiment, I was toying with the idea of “wilds” that could be used in any position of the palindrome.

7. I would love to see these functions written in other programming languages, so if you’re willing I’d love to know about what you create.

### 2 Comments, Comment or Ping

1. If you like palindromes, are you familiar with autograms ( http://en.wikipedia.org/wiki/Autogram )?

2. An interesting trick you might like. If you want to know if something can be rearranged to be a palindrome, you just need to see if there’s at most one element with an odd frequency:

`(->> maybe-palindrome (frequencies) (vals) (filter odd?) (count) (>= 1))`

That’s from memory, so…