How to group strings by prefix

Question

I am writing a Winform UI in which the user must select a single customer. (For reasons beyond my control I am limited to a UI that uses dropdown lists, text fields, checkboxes, radiobuttons only -i.e. no fancy special UI controls)

The situation

• There are a lot of customers (a thousand for example)
• If i put all the customers in a single dropdown there's no way it will be easy for a customer to even see all the customers. Also the it will take too long to retireve all the customers from the DB to populate the dropdown
• My thought is to have two combo box, the first lists groups of the customers by their last name something like a phone book "Aa-Ac", "Ad-Ade", "Adf-B", when selecting the first combo box, it scope the second one to a managable set customer names (no more than for example 40 names)

The question

• I need a reasonable way of grouping their names such that it will be clear to customer which group contains the name. I.e. given a group of names I need to bucketize then int "Aa-Ac".

Comments

• I don't need to solve the general problem of an immense number of names - we know based on our data that 1000 names is the max our users will encounter.
• If there are other techniques please do share, but I am interested specifically in an answer to my specific question around how to determine the buckets ("Aa-Ac", etc.)

Answer 1

Other technique:
I'd combine a ComboBox with a TextBox (is this your textfield? Or did you mean readonly labels?), so the user can type in the some of the first letters and the ComboBox will show all entries starting with these letters. In the case of an exact match it can even skip the usage of the ComboBox and speed up things.

Answer 2

Tanascious' suggestion is mostly on the right track, but I don't think you don't two components. It's been a while since I did any C# development, but if I recall correctly, a single combobox (listbox?) is quite suitable to choose between hundreds of entries because it supports find-as-you-type navigation, i.e. if the name the user is looking for is "Doe, John", typing "do" when the component is selected will take the user within a couple of entries in almost all cases, most of the time to the exact user. It would be less than optimal on a public web page somewhere where everything needs to be clickety-click, but for users working daily with this interface, it's usually no problem.

Answer 3

I think you have to think once or twice before settling on how the gui should work, but in case you really want to go for the bucket idea, you would do something along these lines:

Step 1, create the buckets:

• Decide on a desired bucket size (lets say 40 for the example).
• Sort the names.
• Make the first 40 names the first bucket, the 41-80 names the second bucket etc until you've created all buckets.

Step 2, determine the "names" of the buckets ("Adf-B" etc):

• Lets use bucket[i].Left to refer to the left part of the i'th bucket name ("Adf" above) and bucket[i].Right to the right ("B")
• Lets use bucket[i].Names to refer to the list of the 40 names in this bucket
• Now assuming we have a function that can determine how many characters we have to use to discriminate two strings (lets call it CharsNeeded) we can compare the end/beginning of the buckets next to each other and extract the names from that that.

Like this:

bucket[i].Left = bucket[i].Names.First().Substring(0, CharsNeeded(bucket[i].Names.First(), bucket[i-1].Names.Last()));
bucket[i].Right = bucket[i].Names.Last().Substring(0, CharsNeeded(bucket[i].Names.Last(), bucket[i+1].Names.First()));

CharsNeeded could be implemented like this for example:

int CharsNeeded(string str1, string str2)
{
  int i=0;
  while (i < str1.Length && i < str2.Length && str1[i] == str2[i])
    i++;
  return i + 1;
}

Also, take care in the edge cases, as I did not check for index out of bounds on the bucket-array.