In an alphabet with 28 characters and 4 empty values (denoted by an underscore), how do I optimize a keyboard layout with 4 rows and 8 columns, given a frequency distribution of letter pairs?
The most naive solution that I came up with was to create n random permutations of the alphabet and comparing it to the current best value of the cost function, updating it if better. However, this method is really slow and does not make use of the frequency distribution of letter pairs.
A greedy algorithm seems to be the most intuitive alternative, but I just can't seem to get going. If someone could give be some tips to get going I'd appreciate it. Specifically, how should the next letter be chosen and what is the optimal position to place it in (locally)? I would start with the letter that has the highest sum of frequency starting with that letter, but after that I'm pretty much stuck.