All letter-combinations (n-items) according pattern

Question

Im trying to decrypt a word which letters have been replaced with random other letters (but not 2 different letters into the same one).

The goal:
Im searching for a word which lenght and letter-pattern is known.

What I know:
The pattern itself means if searching for "guests" I know "123454" which shows the position of unique letters in this word. And for sure I know its an english word correctly written.

Software side:
I've created a DataGridView which headers are titled by the pattern. I want to populate each Column (pattern) with its possible combinations of all letters a-z.

What I've tried:
Ill start at the end => I've successfully implemented a spell-checker. So in the end I thought about just going through the columns and check for each result to find the actual word.

From the starting point seen I've written this so far:

private string[] alpha = new string[] { "a", "b", "c", ..."z"};
private int[] digits = new int[] { 0, 1, 2, 3, 4,....9 };

private void bruteforce()
{
    // Each Column
    foreach(DataGridViewColumn col in dgvResults.Columns)
    {
        // HeaderText to CharArray to IntArray (-48 to switch from ASCII to INT).
        int[] pattern = Array.ConvertAll(col.HeaderText.ToCharArray(), c => c - 48);

        // Prepare an result-array with the same length as the pattern.
        string[] resultSet = Enumerable.Repeat("-", pattern.Length).ToArray();

        // For each digit 0-9.
        foreach(int digit in digits)
        {
            // In pattern search for each digit and save the index.
            int[] indexes = pattern.FindAllIndexof(digit);
            // If index is found.
            if(indexes.Length > 0)
            {
                // Custom function ReplaceAtIndex. 
                // Replace resultSet-Values at given Indexes with unique letter
                resultSet.ReplaceAtIndex(indexes, alpha[digit]);
            }
        }
    }
}

Current result:
A pattern of 0112344 will be saved (resultSet) as abbcdee.
Now I would need to loop the letters while staying on the same pattern.

This step feels even more complicated then the stuff before. I thought, before continuing blowing away my head, Im going to see if there are some genius guys out there on stackoverflow who can provide a shorter easier way (maybe some shortcuts with LINQ).

So please, is there anyone thinking "easy doin" about this who could help me? I appreciate every help in here. Thanks

Answer 1

Here is IMO a quite effective algorithm for generating what are you asking for.

It's a variation of the algorithm I've used in Looking at each combination in jagged array and System.OutOfMemoryException when generating permutations and is optimized to perform minimum allocations.

public static class Algorithms
{
    private static readonly char[] alpha = Enumerable.Range('a', 'z' - 'a' + 1).Select(c => (char)c).ToArray();

    public static IEnumerable<string> GenerateWords(this string pattern)
    {
        return pattern.GenerateWordsCore().Select(word => new string(word));
    }

    public static IEnumerable<char[]> GenerateWordsCore(this string pattern)
    {
        var distinctSet = pattern.Select(c => c - '0').Distinct().ToArray();
        var indexMap = pattern.Select(c => Array.IndexOf(distinctSet, c - '0')).ToArray();
        var result = new char[pattern.Length];
        var indices = new int[distinctSet.Length];
        var indexUsed = new bool[alpha.Length];
        for (int pos = 0, index = 0; ;)
        {
            // Generate the next permutation
            if (index < alpha.Length)
            {
                if (indexUsed[index]) { index++; continue; }
                indices[pos] = index;
                indexUsed[index] = true;
                if (++pos < distinctSet.Length) { index = 0; continue; }
                // Populate and yield the result
                for (int i = 0; i < indexMap.Length; i++)
                    result[i] = alpha[indices[indexMap[i]]];
                yield return result;
            }
            // Advance to next permutation if any
            if (pos == 0) yield break;
            index = indices[--pos];
            indexUsed[index] = false;
            index++;
        }
    }
}

Sample usage:

bool test = "12334".GenerateWords().Contains("hello");
foreach (var word in "123454".GenerateWords())
{
    // Do something with word
}