Algorithm for filtering duplicate letters and reassigning available letters for alt menu keys

Question

I have a WinForms application with many menus, each menu contains an average of 30 menu items. In any given menu, there can be several words starting with the same letter.

I am currently using an easy way to create alt key mappings for each item, adding an ampersand to the begging of each menu item.

I need to be able to detect a duplicate key mapping (start letter) and reassign it to another character; this is not yet accepted. The winning character will be closest to the begging of the word as much as possible.

Menu example

• L ist item
• N ew Window
• S ave Document
• P print
• P r int Preview

A more ideal algorithm would be smart enough to look at the next word in a line and have rules for adding. If I could create a set of rules that emulate menus, for example:

I understand that a fire fox most likely assigns them manually, but I try to be constructively lazy.

Answer 1

Since you have an average of 30 elements, there will always be accelerator letters that are used more than once. And you, of course, do not want the letter with the letter to change for several runs (or, even worse, in the same run) of your program.

Why not just save it and require that each menu item has a static accelerator-letter property?

Answer 2

You can consider this as an example of http://en.wikipedia.org/wiki/Hungarian_algorithm . In the language of the article, think about your titles as workers. You want to assign each employee a task, where the task is a letter from AZ. The cost of assigning an employee a letter (task) is a pointer to this letter in the menu item. This minimizes the sum of the indices, so if the first letters are different from each other, the best solution is to use the first letter of each menu item.

Of course, you usually have more letters than menu items. You can get around this by inventing fictitious menu items by charging the same amount for each possible letter assignment to a fictitious menu item.

Answer 3

For the impatient, like me, here is a very clean implementation of the Hungarian alogorim in C # here , and there was a quick test setup to solve the problem. Problem with OP:

Module Module1 Sub Main() test1() End Sub Sub test1() Dim menus() As String = {"File", "Fiddle", "Forest", "Fangle", "Edit", "Entity", "Entropy", "Eviction", "View", "Vixen", "Visible", "Window", "Wait", "What", "Tools", "Time", "Total", "Tea"} Dim items As Integer = menus.GetUpperBound(0) Dim alphabet As String = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" Dim letters As Integer = alphabet.Length - 1 Dim costs(items, letters) As Integer Dim cost As Integer Dim ch As String Dim o As Integer Dim longest As Integer = 0 For i = 0 To items cost = 1 If menus(i).Length > longest Then longest = menus(i).Length End If For j = 0 To menus(i).Length - 1 ch = menus(i).Substring(j, 1) o = alphabet.IndexOf(ch, StringComparison.InvariantCultureIgnoreCase) If costs(i, o) = 0 Then ' Don't overwrite when same letter more than once in word costs(i, o) = cost cost += 2 End If Next For j = 0 To letters If costs(i, j) = 0 Then costs(i, j) = 99 End If Next Next longest += 1 For r = 1 To 2 Console.Write("".PadRight(longest)) For i = 0 To letters Console.Write(alphabet.Substring(i, 1).PadLeft(3)) Next Console.WriteLine("") For i = 0 To items Console.Write(menus(i).PadRight(longest)) For j = 0 To letters Console.Write(costs(i, j).ToString.PadLeft(3)) Next Console.WriteLine("") Next If r = 1 Then Dim h As New HungarianAlgorithm Dim result() As Integer result = h.FindAssignments(costs) Console.WriteLine("Answer:") For i = 0 To items Console.WriteLine(menus(i).PadRight(longest) & alphabet.Substring(result(i), 1)) Next End If Next r End Sub 

End module