Create all words that correspond to a telephone digit sequence

Question

I wrote a terrible function to map E.161 keys to letter strings.

I think the logic could be simplified using a recursive function; however I have never been good at recursive methods. Any suggestions are welcomed.

My Code:

#LINQPad optimize+
void Main()
{
    var summary = BenchmarkRunner.Run<MyClass>();
    summary.Dump();
}

public class MyClass
{

    [Params("2", "24", "247", "2474", "24747")]
    public string DTMF_Input { get; set; }

    List<char> DTMFtoString(char c)
    {
        return c switch
        {
            '2' => new List<char>() { 'A', 'B', 'C' },
            '3' => new List<char>() { 'D', 'E', 'F' },
            '4' => new List<char>() { 'G', 'H', 'I' },
            '5' => new List<char>() { 'J', 'K', 'L' },
            '6' => new List<char>() { 'M', 'N', 'O' },
            '7' => new List<char>() { 'P', 'Q', 'R', 'S' },
            '8' => new List<char>() { 'T', 'U', 'V' },
            '9' => new List<char>() { 'W', 'X', 'Y', 'Z' },
            _ => throw new ArgumentOutOfRangeException($"The specified character '{c}' is not supported."),
        };
    }

    [Benchmark]
    public void GetCombosFromDTMF()
    {
        var Tones = new System.Collections.Generic.Stack<char>(DTMF_Input.ToCharArray().Reverse());

        var MyPrefixes = new List<string>();
        while (Tones.Any())
        {
            var Combos = new List<string>();
            var entries = DTMFtoString(Tones.Pop());
            if (MyPrefixes.Any())
            {
                foreach (var existing in MyPrefixes)
                {
                    foreach (var newTone in entries)
                    {
                        Combos.Add(existing + newTone);
                    }
                }
            }
            else
            {
                Combos = entries.Select(c => Char.ToString(c)).ToList();
            }

            MyPrefixes = Combos;
        }

        MyPrefixes.OrderBy(r => r).ToList();
    }
}

Benchmarks

|            Method | DTMF_Input |         Mean |       Error |      StdDev |
|------------------ |----------- |-------------:|------------:|------------:|
| GetCombosFromDTMF |          2 |     671.0 ns |    11.26 ns |    10.54 ns |
| GetCombosFromDTMF |         24 |   1,537.1 ns |    25.25 ns |    21.09 ns |
| GetCombosFromDTMF |        247 |   8,690.2 ns |   160.62 ns |   134.12 ns |
| GetCombosFromDTMF |       2474 |  30,870.3 ns |   557.15 ns |   762.63 ns |
| GetCombosFromDTMF |      24747 | 168,660.9 ns | 3,008.75 ns | 3,344.22 ns |

Answer 1

If you are unhappy with the DTMFtoString method then here is my suggestion:

Rather than recreating a List<char> for each and every method call, use a Dictionary<char, List<char> structure and perform a lookup.

Dictionary<char, List<char>> DTMFLookup = new()
{
    { '2', new List<char>() { 'A', 'B', 'C' }},
    { '3', new List<char>() { 'D', 'E', 'F' }},
    { '4', new List<char>() { 'G', 'H', 'I' }},
    { '5', new List<char>() { 'J', 'K', 'L' }},
    { '6', new List<char>() { 'M', 'N', 'O' }},
    { '7', new List<char>() { 'P', 'Q', 'R', 'S' }},
    { '8', new List<char>() { 'T', 'U', 'V' }},
    { '9', new List<char>() { 'W', 'X', 'Y', 'Z' }}
};

With this approach you allocate memory only once.

If you want to make this lookup table immutable then you can do that like this

static readonly ImmutableDictionary<char, ImmutableList<char>> DTMFLookup = new Dictionary<char, List<char>>()
{
    { '2', new List<char>() { 'A', 'B', 'C' }},
    { '3', new List<char>() { 'D', 'E', 'F' }},
    { '4', new List<char>() { 'G', 'H', 'I' }},
    { '5', new List<char>() { 'J', 'K', 'L' }},
    { '6', new List<char>() { 'M', 'N', 'O' }},
    { '7', new List<char>() { 'P', 'Q', 'R', 'S' }},
    { '8', new List<char>() { 'T', 'U', 'V' }},
    { '9', new List<char>() { 'W', 'X', 'Y', 'Z' }}
}.ToImmutableDictionary(kp => kp.Key, kp => kp.Value.ToImmutableList());

And finally the lookup code:

var @char = Tones.Pop();
if (!DTMFLookup.TryGetValue(@char, out var entries))
    throw new ArgumentOutOfRangeException($"The specified character '{@char}' is not supported.");

Answer 2

I wonder if you really wanted a code review, or if you really wanted help on creating a recursive version in hopes of better performance. One would think recursion should be faster, particularly since you (1) reverse the input digits to create the combinations of words (what you call MyPrefixes), and then (2) re-order MyPrefixes, which at its heart is simply reversing the combinations.

All of this suggests that maybe there is a better way.

Since benchmarks very per machine, here are bench marks of your original code on my laptop:

Method	DTMF_Input	Mean	Error	StdDev
GetCombosFromDTMF	2	514.8 ns	8.01 ns	7.49 ns
GetCombosFromDTMF	24	1,232.3 ns	14.71 ns	11.49 ns
GetCombosFromDTMF	247	7,148.6 ns	127.21 ns	130.63 ns
GetCombosFromDTMF	2474	24,246.7 ns	381.71 ns	318.74 ns
GetCombosFromDTMF	24747	134,660.1 ns	981.09 ns	765.97 ns

I have other versions that did not improve the times that much, if at all. My 2nd attempt was using @PeterCsala 's dictionary suggestion returning List<char>, and the 3rd returned char[] instead.

My 4th version used recursion where I process the input digits in the order they are given. This has benefit of also producing the output in the desired order. I am using .NET 6 on a Windows 10 laptop. Confession: bench marking is not my strong suit. I had to fumble around with NuGet to install BenchmarkDotNet package. I could not find an equivalent for summary.Dump().

using BenchmarkDotNet.Parameters;
using BenchmarkDotNet.Running;
using BenchmarkDotNet.Attributes;

var summary = BenchmarkRunner.Run<MyClass>();

public class MyClass
{

    [Params("2", "24", "247", "2474", "24747")]
    public string DTMF_Input { get; set; }

    Dictionary<char, char[]> DTMFLookup = new()
    {
        { '2', new char[] { 'A', 'B', 'C' } },
        { '3', new char[] { 'D', 'E', 'F' } },
        { '4', new char[] { 'G', 'H', 'I' } },
        { '5', new char[] { 'J', 'K', 'L' } },
        { '6', new char[] { 'M', 'N', 'O' } },
        { '7', new char[] { 'P', 'Q', 'R', 'S' } },
        { '8', new char[] { 'T', 'U', 'V' } },
        { '9', new char[] { 'W', 'X', 'Y',  'Z' } }
    };


    [Benchmark]
    public void GetCombosFromDTMF()
    {
        var digits = DTMF_Input.ToCharArray();
        var word = new char[digits.Length];  // Same array used repeatedly for recursion
        var combinations = GetCombinationsRecursively(digits, word, index: 0);
        // I don't know if BenchMarkDotNet requires IEnumerables to be realized as a List.
        var words = combinations.ToList();
    }

    private IEnumerable<string> GetCombinationsRecursively(char[] digits, char[] word, int index)
    {
        if (!DTMFLookup.TryGetValue(digits[index], out var letters))
            throw new ArgumentOutOfRangeException($"The specified character '{digits[index]}' is not supported.");

        bool keepRecursing = index < (digits.Length - 1);

        foreach (var letter in letters)
        {
            word[index] = letter;
            if (keepRecursing)
            {
                var collection = GetCombinationsRecursively(digits, word, index + 1);
                foreach (var item in collection)
                {
                    yield return item;
                }
            }
            else
            {
                yield return new string(word);
            }
        }
    }

}

The results are significantly better:

Method	DTMF_Input	Mean	Error	StdDev
GetCombosFromDTMF	2	126.7 ns	2.51 ns	2.58 ns
GetCombosFromDTMF	24	496.1 ns	9.42 ns	9.25 ns
GetCombosFromDTMF	247	2,091.7 ns	18.58 ns	15.52 ns
GetCombosFromDTMF	2474	6,985.7 ns	75.83 ns	59.20 ns
GetCombosFromDTMF	24747	29,454.0 ns	572.26 ns	744.10 ns

For a small number of digits, the times are cut in half. As you add more digits, the times are cut by 1/3 to 1/4. I'd like to think that what I have could be improved somewhat, both in performance and code maintenance, but the main reason for my answer was to show that recursion should be pursued.