Applying Combinatorial Optimization to Keyboard Layouts

[Xichekolas]

One of my interest areas in grad school is the idea of combinatorial optimization (picking the best answer for an NP-hard problem). The optimum layout of a keyboard falls in this category, since there are on the order of 61! possible layouts for just the main typing area. (61! is roughly 5x10^83)

Examining every single possible layout isn't possible. Even if you were to reduce the problem to only the 26 letter keys, and you tested 1000 layouts every second, it would take you 10,000 trillion years to try them all.

Hence approximation algorithms. Given a way to measure the 'quality' of a layout, these algorithms seek to get very close to an optimum solution, but they can't guarantee that it is _the_ optimum solution (since they haven't looked at every possible one).

This guy has done just that (using simulated annealing):

http://mkweb.bcgsc.ca/carpalx/?

For fun, I'm doing roughly the same thing with a different approach (ant colony optimization), but I thought I'd link to his page, because it's very interesting reading. He lists a particular layout that is his best so far (QGMLWY), and provides a download of various mappings.

[AndrewZorn]

carpalx was the second site i went to which confirmed my idea to go to colemak
pretty opimized while keeping some keys like QWERTY for shortcuts and learning purposes

but even though i am new to colemak i dont want to switch again
and until it gains SOME popularity it might be a bad idea
as what if a better study is done

[Xichekolas]

pretty optimized while keeping some keys like QWERTY for shortcuts and learning purposes

Yeah I'm currently a dvorak user (for about five years now). I was considering colemak, but it's by no means as standard as dvorak or qwerty (it's made it into X windows, but not the default linux keymaps or the windows ones). So I figured if I have to carry around a colemak keymap file on a usbstick, I might as well carry around a QGMLWY one.

FWIW, QGMLWY keeps the ZXCV keys in the same place too.

[AndrewZorn]

windows does not have it but latest version of X does
so any graphical linux system
or any windows one with internet access

i guess what i meant above was that carpalx basically invented and remains the only supporter of QGMLWY.  i know everyone starts somewhere but a lot of my reasoning for colemak over dvorak was ensuring at least some part of the world knows about it

as if i fear the UN is going to have a meeting on the news tomorrow to discuss the voting of the new world standard keyboard, and QGMLWY wont be on the ballot

stupid i know
because using colemak already pretty much alienates myself

[huha]

He lists partially-optimized keyboard layouts by swapping only a small number of keys. Is this a feature of his program you can try yourself or just an artifact from development?
I'm fairly proficient with the German keyboard layout already, but swapping a few letters doesn't sound like much of a problem, so I'd like to try this myself, but I don't quite want to waste countless hours finding out what to do when it turns out to be impossible with the program. Did anyone already try this?

-huha

[talis]

It would be interesting to know how the optimization solution would converge initialized with a simple key frequency optimization.  Its possible that the first order optimization would get you near a strong local minima.

It would also be interesting to see how the solutions converged given different corpora, eg would a strongly code based corpus end up with a completely different optimization then a purely text based corpus, or would they converge to similar places (and how much worse a coder optimized layout would be on plain text).

[Xichekolas]

He lists partially-optimized keyboard layouts by swapping only a small number of keys. Is this a feature of his program you can try yourself or just an artifact from development?

One of the config files (etc/mask/letters.conf) controls which keys can be swapped and which are locked. The default is that only letters can move... all symbols and numbers are stationary.

[Shawn Stanford]

Crikey, I can't even imagine trying to change layouts after 30+ years of touch-typing. It's all I can do to adjust to a new cursor T when moving from a Model M to a Unicomp 122 to my laptop.

Scary...