String combinations with multi-character replacement

Question

According to the entered license plate (eg. ABC123) and a list of replacement values (eg 1 replaced by I). I need to get all possibles combinations.

For example:

1 => I
3 => B
A => H
0 (zero) => O
O => 0 (zero)

Input :

ABC123

Expected output :

ABC123, ABCI23, ABCI28, ABC128, HBC123, HBCI23, HBCI28, HBC128

I tried with String Combinations With Character Replacement, but I can't...

Post what you've tried, doesn't matter if it worked or not. – Xiaoy312 Apr 27 '16 at 21:50 — Xiaoy312, Apr 27 '16 at 21:50

Arturo Menchaca · Answer 1 · 2016-04-28T02:04:33.480

2

You can do it using recursion, iterate for each character and call recursively using the original character and the replacement, something like this:

public static IEnumerable<string> Combinations(string s, Dictionary<char, char> replacements)
{
    return Combinations(s, replacements, 0, string.Empty);
}

private static IEnumerable<string> Combinations(string original, Dictionary<char, char> replacements, int index, string current)
{
    if (index == original.Length) yield return current;
    else
    {
        foreach (var item in Combinations(original, replacements, index + 1, current + original[index]))
            yield return item;

        if (replacements.ContainsKey(original[index]))
            foreach (var item in Combinations(original, replacements, index + 1, current + replacements[original[index]]))
                yield return item;
    }
}

And call this methods like so:

Dictionary<char, char> dict = new Dictionary<char,char>();
dict['1'] = 'I';
dict['3'] = 'B';
dict['A'] = 'H';
dict['O'] = '0';
dict['0'] = 'O';

var combs = Combinations("ABC123", dict);

edited Apr 28 '16 at 02:04

answered Apr 27 '16 at 21:58

Arturo Menchaca

15,783
1
29
53

Great answer @ArturoMenchaca - I'm using this, but if I wanted all the combinations for "1" to be adjusted to "I" AND "L", how is this best achieved? I did try adjusting your code to be a dictionary of but then I started to wonder whether it's even possible, I then copy and pasted the code with the two variants, then merged the results together into a distinct set. Just wondered how it *should* be done. – RobbiewOnline Oct 16 '17 at 10:00
@DevologyLtd: You can use a char[] as you said, then in the `if (replacements.ContainsKey...` statement add `foreach (var replace in replacements[original[index]])` before the recursive call, and replace in the call `current + replacements[original[index]]` with `current + replace`. – Arturo Menchaca Oct 16 '17 at 14:54
I can't wrap my head around doing the enumerators / return yield in Java. I've raised https://stackoverflow.com/questions/49371495/string-combinations-with-multi-character-replacement-yield-return-alternative-r and wondered whether you could help @ArturoMenchaca – RobbiewOnline Mar 19 '18 at 20:06

score 0 · Answer 2 · edited May 23 '17 at 10:28

It can easily be done by utilizing the algorithm from my answer to Looking at each combination in jagged array:

public static class Algorithms
{
    public static IEnumerable<string> GetCombinations(this char[][] input)
    {
        var result = new char[input.Length]; 
        var indices = new int[input.Length];
        for (int pos = 0, index = 0; ;)
        {
            for (; pos < input.Length; pos++, index = 0)
            {
                indices[pos] = index;
                result[pos] = input[pos][index];
            }
            yield return new string(result);
            do
            {
                if (pos == 0) yield break;
                index = indices[--pos] + 1;
            }
            while (index >= input[pos].Length);
        }
    }
}

by adding the following method:

public static IEnumerable<string> GetCombinations(this string input, Dictionary<char, char> replacements)
{
    return input.Select(c =>
    {
        char r;
        return replacements.TryGetValue(c, out r) && c != r ? new[] { c, r } : new[] { c };
    }).ToArray().GetCombinations();
}

Sample usage:

var replacements = new Dictionary<char, char> { { '1', 'I' }, { '3', '8' }, { 'A', 'H' }, { '0', 'O' }, { 'O', '0' } };
var test = "ABC123".GetCombinations(replacements);
foreach (var comb in test) Console.WriteLine(comb);

String combinations with multi-character replacement

2 Answers2

Linked