CODEWITHSUNDEEP
algorithmgraphgenetic-algorithmgreedygenetic-programming
Joel Sanfeliu
Joel Sanfeliu

Reputation: 1

Allocate letters to an NxM grid to minimize the distance between letter pairs that show up frequently in a given list of words

Given a input of a lot of words and an NxM dimension I have to create an algorithm that designs the best (if possible, or one of the bests) single-finger NxM keyboard layout for mobile. Which means that, for example, given a letter in the keyboard it's better to have closer letters that you know that with highly probability will come next. An other statement could be that the middle part of the keyboard is best to reach from the finger so it should be the most frequent letter, so the most important letters should concentrate in the middle meanwhile you consider what I said before about you have closer letters that you know that with highly probability will come next and also you consider the NxM keyboard layout. The frequency of each letter and what letters come next after a certain letter it's easy to get by reading the input words and storing it in a data structure, but once I have this I don't know how to do this algorithm.

Obviously you have to find the best combination of letters in the keyboard layout so this if you do it by brute force it's exponential and it's impossible to do it in an efficient way. But even if I could, I don't even know how to judge each combination and know which one is the best. I though about making it a graph and get something or even the google's pagerank algorithm which has a similarity, but I got stuck. I also thought about genetic algorithms which would be so efficient to find the best or one of the best, which that's enough. I don't know if I explained myself clearly, if not I'll try to explain it in different words or something. Thanks.

Upvotes: 0

Views: 61

Answers (1)

ravenspoint
ravenspoint

Reputation: 20596

Assumption: Common letters are best in the center of keyboard

  • Assign score to keyboard positions ( p )

    Score(xp,yp) = abs(N/2 - xp) + abs(M/2 - yp )

  • Assign score to common letters

    • ignore pairings
    • sort letters into increasing frequency
    • score( l ) = index of l in sorted letters

  • Objective function

    O = sum over all l ( score( l ) * score ( xl, yl )

  • Optimize O using linear programming

Assumption: Common letter pairs are best as neighbors

  • Order letter pairs into increasing frequency
  • score( l1, l2 ) = index of l1,l2 in sorted pairs
  • Assign score to neighbor positions

score( p1, p2 ) = Pythagorean distance between p1,p2

  • Objective function

O = sum over all pl1,l2 ( score(l1,l2 ) * score ( l1p, l2p ) )

Note: This objective function is intractable. If youR input test is of any significant length then the number of letter pairs will approach 26 * 26 ( assuming English and lower case ) - suggest you just count the 10 or so most frequent. Then you will have to use random search or hill climbing to explore the the objective function. It might be a good idea to initialize hill climbing with an arrangement generated by a greedy algorithm, placing the most frequent letter pairs adjacent to each other until there is no more room.

( Perhaps you begin to see why, after all these years, we are still stuck with QWERTYUIOP :-)

Upvotes: 0

Related Questions