Iterating non-square (sort of) matrix

Question

I have a dictionary like this (sample data thus it doesn't make sense):

Dictionary<char, string[]> codes = new Dictionary<char, string[]>();

string[] is an array of possible replacements for the Dictionary's key.

Filling up the dictionary with some sample data...

codes.Add("A", new string[] {"噅噅", "裧", "頖", "11"});
codes.Add("B", new string[] {"垥", "2", "鉠"});
codes.Add("C", new string[] {"33", "韎"});
codes.Add("D", new string[] {"櫋", "緟", "嘕", "鈖", "灡", "犅"});
...
codes.Add("T", new string[] {"濇", "汫", "岕", "5"});
...

Now lets "encode" the following word:

    char[] charArray = "act".ToCharArray();
    foreach (char c in charArray) {
       string[] replacements = codes[c].Where(x => !String.IsNullOrEmpty(x)).ToArray();//removing empty elements

       ...
    }

I cannot wrap my head now on what to do next, I want to have a list of all possible combinations, it should return a list like this (for the word "act"):

噅噅韎5

裧33濇

裧33汫

裧33岕

裧335

裧韎濇

裧韎汫

裧韎岕

...

Can't show all combinations because of stackoverflow's spam filter...

@dharms interesting. Where should I call the recursive method? For each "key" ? — Cornwell, May 11 '16 at 19:33
Pass in two strings, what you want encoded and the current branch's encoded string so far. First call would look something like `Encode("act", "");` — Dan Harms, May 11 '16 at 19:53
@dharms sorry, I'm a bit lost. Won't I need to pass the character I want to encode instead of the full original string? — Cornwell, May 11 '16 at 19:58
Passing one character at a time will not get you what you need. The process would be take the first character of incoming string, and for each possible encoding of that character, recursively call with remaining string (excluding first character), and the encoded character added to the second parameter string. — Dan Harms, May 11 '16 at 20:29

score 1 · Accepted Answer · edited May 23 '17 at 11:44

The post title is misleading. If I understand correctly, you want to generate all the combinations using the codes as input char replacements.

I have answered a similar question (String combinations with multi-character replacement), however due to string[] part I cannot reuse directly the handy code from Looking at each combination in jagged array, so instead I'll just utilize the same algorithm for your case:

public static class Algorithms
{
    public static IEnumerable<string> GetCombinations(this string input, Dictionary<char, string[]> replacements)
    {
        var map = new string[input.Length][];
        for (int i = 0; i < map.Length; i++)
        {
            var c = input[i];
            string[] r;
            map[i] = replacements.TryGetValue(c, out r)
                && (r = r.Where(s => !string.IsNullOrEmpty(s)).ToArray()).Length > 0 ?
                r : new string[] { c.ToString() };
        }
        int maxLength = map.Sum(output => output.Max(s => s.Length));
        var buffer = new char[maxLength];
        int length = 0;
        var indices = new int[input.Length];
        for (int pos = 0, index = 0; ;)
        {
            for (; pos < input.Length; pos++, index = 0)
            {
                indices[pos] = index;
                foreach (var c in map[pos][index])
                    buffer[length++] = c;
            }
            yield return new string(buffer, 0, length);
            do
            {
                if (pos == 0) yield break;
                index = indices[--pos];
                length -= map[pos][index].Length;
            }
            while (++index >= map[pos].Length);
        }
    }
}

Test:

var codes = new Dictionary<char, string[]>();
codes.Add('A', new string[] { "噅噅", "裧", "頖", "11" });
codes.Add('B', new string[] { "垥", "2", "鉠" });
codes.Add('C', new string[] { "33", "韎" });
codes.Add('D', new string[] { "櫋", "緟", "嘕", "鈖", "灡", "犅" });
//...
codes.Add('T', new string[] { "濇", "汫", "岕", "5" });
//...

var test = "ACT".GetCombinations(codes).ToList();

Iterating non-square (sort of) matrix

1 Answers1