Finding the number of combinations of letters such that each letter equals a number

Question

I am trying to find out the algorithm for the following using C#: having a=1, b=2, c=3 etc to z. When given a string of numbers I need to calculate the number of combinations of alphabets. For example, for input: '123', the output would be 3 since '1'+'2'+'3'=abc, '1'+23'=aw, '12'+'3'=lc

I know there should be a recursive function to go through each number. And inside the function there should be a loop. And if the number is greater than 26 skip that combination.

Here is what I have been trying so far:

    static void Main(string[] args)
    {
       int no_combination = getCombinations("123");
    }
    public int getCombinations(string str)
    {
        char[] numbers = str.ToCharArray();
        List<string> combinatins = new List<string>();
        int no_combinations = getPossibilities(numbers, 0, out combinatins);
        return no_combinations;
    }
    public int getPossibilities(char[] numbers, int index, out List<string> combinations)
    {

        combinations = new List<string>();

        int possibilities = 0;

        string combination = "";
        for (int i = index; i < numbers.Length; i++)
        {
            combination += numbers[i] + " ";
        }
        combinations.Add(combination);
        possibilities = combinations.Count;
        if (index>=numbers.Length)
        {
            return possibilities;
        }
        getPossibilities(numbers, ++index, out combinations);

        return possibilities;
    }

I know there are logical errors. The combinations list is getting reset in each call. And the way the combinations are created is missing a tweak that I can't get. I am not expecting to write the whole code. Helpful hints would be appreciated.

Related : http://stackoverflow.com/questions/3093622/generating-all-possible-combinations — , Aug 05 '16 at 23:41
Without analyzing your code. Here is a sketch: Given your recursive function F and a string S. F calls itself two times: (1): it consumes one number (shorten S by first element) & converts to number; then calls itself with shortened S and the already constructed string. (2): it consumes two numbers (shorten S by first two elements) & converts to number; if not possible: return empty! If possible: call itself with shortened S and the already constructed string. All these functions could return the final string then; collect them all at top-F & build a set and count or do whatever you want. — sascha, Aug 05 '16 at 23:43
I remember seeing and solving this problem somewhere but can't remember where. Can you post a link so that we can test our solutions? — EvilTak, Aug 06 '16 at 06:49

score 0 · Answer 1 · answered Aug 06 '16 at 00:11

The solution is the following:

Step through your input string.
If the input string starts with a number, that is the beginning of a combination. Continue recursively onwards where the new input parameter is the string with the matched number removed.
If the input string is equal exactly to the number, the combination is over.

I wrote the solution to your problem in Python. May this serve as a guide for you as you write it in C#.

# Create the lookup object
# chr(97) == 'a'
lookup = dict()
for i in range(97, 97+26):
    lookup[str(i-96)] = chr(i)

# Calculate the combinations
def get_combinations(inp, combinations=set(), fragment=()):
    for key, value in lookup.items():
        if inp == key:
            combinations.add(fragment + (key,))
        elif inp.startswith(key):
            combinations = combinations.union(get_combinations(inp[len(key):], combinations, fragment + (key,)))
    return combinations

combinations = get_combinations('123')
for combination in combinations:
    str_combination = tuple(lookup[x] for x in combination)
    print(combination, str_combination)

The output of the above program is this:

('1', '2', '3') ('a', 'b', 'c')
('1', '23') ('a', 'w')
('12', '3') ('l', 'c')

... Or, if you're only interested in the length, 3

score 0 · Answer 2 · answered Aug 06 '16 at 05:55

This works:

Func<int, IEnumerable<string>> combinations =
    n =>
    {
        Func<string, IEnumerable<IEnumerable<string>>> fracture = null;
        fracture = x =>
            String.IsNullOrEmpty(x)
            ? new [] { Enumerable.Empty<string>() }
            : Enumerable
                .Range(1, x.Length)
                .SelectMany(y =>
                    fracture(x.Substring(y))
                    .Select(z =>
                        new [] { x.Substring(0, y) }
                            .Concat(z)));

        return fracture(n.ToString())
            .Select(x => x.Select(y => int.Parse(y) + 'a' - 1))
            .Where(x => x.All(y => y >= 'a' && y <= 'z'))
            .Select(x => String.Join("", x.Select(y => (char)y)));
    };

So, combinations(123) would then produce:

abc 
aw 
lc

If you'd rather it as regular methods then this is it:

public IEnumerable<string> Combinations(int n)
{
    return Fracture(n.ToString())
        .Select(x => x.Select(y => int.Parse(y) + 'a' - 1))
        .Where(x => x.All(y => y >= 'a' && y <= 'z'))
        .Select(x => String.Join("", x.Select(y => (char)y)));
}

public IEnumerable<IEnumerable<string>> Fracture(string x)
{
    return String.IsNullOrEmpty(x)
        ? new [] { Enumerable.Empty<string>() }
        : Enumerable
            .Range(1, x.Length)
            .SelectMany(y =>
                Fracture(x.Substring(y))
                .Select(z =>
                    new [] { x.Substring(0, y) }
                        .Concat(z)));
}

score 0 · Answer 3 · answered Aug 06 '16 at 07:52

A simple (albeit not clean) implementation (with memoization) only for the number of combinations in Python:

cache = {}
def num_comb_dp(s):
    if s in cache:
        return cache[s]

    if len(s) <= 2:
        return len(s) if int(s) <= 26 else len(s) - 1

    val = num_comb_dp(s[1:]) + (num_comb_dp(s[2:]) if int(s[0:2]) <= 26 else 0)
    cache[s] = val
    return val

Without memoization:

def num_comb_no_dp(s):
    if len(s) <= 2:
        return len(s) if int(s) <= 26 else len(s) - 1

    return num_comb_no_dp(s[1:]) + (num_comb_no_dp(s[2:]) if int(s[0:2]) <= 26 else 0)

The version with memoization is much faster, as can be seen in the CodeSkulptor link. Test it on CodeSkulptor here.

Implementation in C# can be found in this .NetFiddle.

The solution is based on the fact that the problem involves overlapping sub-problems (and thus also is a candidate for memoization).

Let's go through the base conditions available here:

Any string with length 1 will always yield one combination.
A string with length 2 will yield at least one combination (both individual digits can be converted to an alphabet). A second combination will only be yielded if the integer value of the string is less than equal to 26 (for we have 26 alphabets)

Now that we have established the base conditions, we can use them to establish the cases we need to check.

A combination of a string can have two possibilities:

<COMB> = <digit> + <COMB>
<COMB> = <digit> + <digit> + <COMB>

For a given string, there are two possible combinations: One in which the first digit is considered and the second in which the first two digits are considered. Therefore, the number of combinations for a string will be the sum of number of combinations considering only the first digit and number of combinations considering the first two digits.

We know for sure that the first case will always yield some number of combinations, since a single digit can be represented as an alphabet. The second case, however, will only yield combinations if the first two digits form an alphabet, that is a number <= 26.

Now that we have laid all this down, we can move on to the solution, which can be found in this DotNetFiddle and below. The code and comments should be self explanatory.

    private static int GetNumberOfCombinations(string s)
    {
        // No need of recomputing the value if we already have
        if (cache.ContainsKey(s))
            return cache[s];

        // The following combines two conditions:
        // If length is 1, 1 combination possible
        // If length is 2, 1 combination is possible for sure, and 
        // 2nd combination is only valid if first two digits form an alphabet.
        if (s.Length <= 2)
            return int.Parse(s) <= 26 ? s.Length : s.Length - 1;

        int value = GetNumberOfCombinations(s.Substring(1));

        // If the first two digits form an alphabet,
        // Then only process those combinations
        if (int.Parse(s.Substring(0, 2)) <= 26)
            value += GetNumberOfCombinations(s.Substring(2));

        // Store in cache
        cache[s] = value;

        return value;
    }

Finding the number of combinations of letters such that each letter equals a number

3 Answers3