Optimum phone keypad layouts, or, what to do with a boring weekend.

So, I was a little bored, and had an idea. The commonly used (alphabetic) phone keypad layout is not particularly efficient when it comes to T9 (one digit per letter) style entry - there are a lot of collisions. What would an ideal keypad layout look like?

So I hunted up a computer-readable english dictionary with frequency scores (a 0-16 scale), and devised a way to score the efficiency of a layout: group words by the digits they translate into with that layout, and multiply together their frequency scores. So, for example, two colliding words with frequency 8 would score 64 points, while a collision between a word with frequency 1 and one with frequency 15 would score only 15 points. The idea is that collisions between words with greatly different frequencies are much easier to resolve - it'll almost always be the more common word - whilst collisions between similar words are generally bad. Then, sum up all the products to get the final score.

I then seeded a Genetic Algorithm with the default keypad layout, and ran generations of randomly mutating layouts (by reassigning letters at random) then scoring them, then selecting the few layouts with the lowest scores, and repeating.

The default keypad layout scores a whopping 8,853,348 points.
The most optimal layout I could find scores only 71,063 points. The layout was:

{gr',aky,cej,lw-,fimxz,hn,ps,qtu,bdov}

Various variations on the placing of the apostrophe and hyphen also had the same score.
Each group represents letters to go on one key - order doesn't matter for the purpose of this.

This was a 40th generation result of the original (generation 0) default layout. I have a complete 'geneaology', of course. This was the best run of several I did totally from scratch - the best results seem to occur when I select a reasonably large 'breeding population', not just the few very fittest ones - the geneaology for the winner has several steps where the parent scored better than the child.

I just found it interesting how incredibly inefficient the default layout is when it comes to collisions. A pity nobody will ever use anything else.

The next step, of course, would be to construct another GA based on the optimum keypad layout for this key mapping, so as to minimise finger movement between letters when typing a large corpus.