Permuting beyond one collection

Hello:

I am trying to create all combination of a structure that looks like
the following:

a a p w

b b q x

c c r y

t z

where the columns represent a char[]. Now, what I want is the
following:

aapw
aapx
aapy
aapz
aaqw
aaqx
aaqy
aaqz
etc.

Now, I know that the number of permutations is length of each column
multiplied together. Here is a solution I made that is all right, but
I know there must be a better way (in C#):

public static void Main()
{
using (OrderedSet<string> words = new
OrderedSet<string>(Functional.Less<string>))
{
// populate the dictionary - file presorted, one word
per line
using (StreamReader reader = new
StreamReader(File.OpenRead(@"E:\Repertoire\data\words.txt")))
{
string line;
while ((line = reader.ReadLine()) != null)
{
words.Add(line.Trim().ToLower());
}
}

Regex onlyNumbers = new Regex(@"[2-9]+",
RegexOptions.Compiled);
char[][] values =
{
new char[]{ 'a', 'b', 'c' },
new char[]{ 'd', 'e', 'f' },
new char[]{ 'g', 'h', 'i' },
new char[]{ 'j', 'k', 'l' },
new char[]{ 'm', 'n', 'o' },
new char[]{ 'p', 'q', 'r', 's' },
new char[]{ 't', 'u', 'v' },
new char[]{ 'w', 'x', 'y', 'z' }
};
while (true)
{
// Get the number from the user
string number = Console.In.ReadLine();

// check that it is valid
if (onlyNumbers.IsMatch(number))
{
// get all possible values for each number
ArrayList<char[]> possibleValues = new
ArrayList<char[]>();
foreach (char c in number)
{
possibleValues.Add(values[(int)c - '2']);
}

// permute over all combinations
ArrayList<string> options = new
ArrayList<string>();
for (int i = possibleValues.Count - 1; i >= 0;
--i)
{
char[] list = possibleValues[i];
ArrayList<string> newOptions = new
ArrayList<string>();
foreach (char c in list)
{
if (i == possibleValues.Count - 1)
{
newOptions.Add(new string(c, 1));
}
else
{
for (int j = 0; j !=
options.Count; ++j)
{
newOptions.Add(c +
options[j]);
}
}
}
options = newOptions;
}

// Display found words
foreach (string option in options)
{
if (words.Contains(option))
{
Console.Out.WriteLine(option);
}
}
}
}
}
}

This program will take phone numbers, excluding 0 and 1 and generate
all the possible words that could be made from the inputted numbers
(of any length). I do it now by appending all the current column's
letters to the fronts of all the existing substrings. This way I am
building my words from back to front. However, I know this could be a
much better solution if I could generate full-words and process them
as I go.

The idea came from my coworkers (he doesn't want me to tell him how to
write it), and it turned out to be really interesting.

Thanks for your replies!

~Travis
.

Relevant Pages

  • Re: checking to see if a string contains every letter of the alpha
    ... Using a bitmap might be more efficient than allocating a hash table ... ... foreach (char ch in str) ... > foreach(char c in string.ToCharArray()) ... >> see if a string contains every letter of the alphabet. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Integer conversion to Binary Coded Decimal
    ... foreach (char c in char ) ... then combine the items in the string into 8 character strings and convert ... something I thought the framework would provide. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Fast way to read string one char at a time
    ... string one char at a time. ... fairly good idea as to why the "for" loop is fast. ... the "foreach" loop is pretty much unusable because I'm not really going to ... string given an char index. ...
    (microsoft.public.dotnet.framework.performance)
  • Re: foreach with a string and Hashtable
    ... The foreach uses the IEnumerable interface to enumerate through the ... enumerates the characters in the string. ... from the linetext variable rather than each character. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: System.AccessViolationException
    ... internal string theAP; ... DataColumn col = new DataColumn; ... private string _pwd; ... foreach ...
    (microsoft.public.dotnet.languages.csharp)