求字母组合的数目，使每个字母等于一个数字

本文关键字：数字 于一个 组合 | 更新日期: 2023-09-27 18:01:01

我正在尝试使用C#找出以下内容的算法：具有a＝1，b＝2，c＝3等到z。当给定一串数字时，我需要计算字母组合的数量。例如对于输入："123"，输出将是3，因为"1'+'2'+'3'=abc，"1'+23'=aw，"12'+'3'=lc

我知道应该有一个递归函数来遍历每个数字。在函数内部应该有一个循环。如果数字大于26，则跳过该组合。

以下是我迄今为止一直在尝试的内容：

    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;
    }

我知道存在逻辑错误。组合列表在每次调用中都会重置。组合的创建方式缺少了一个我无法得到的调整。我不希望写完整的代码。如有帮助，我们将不胜感激。

求字母组合的数目，使每个字母等于一个数字

解决方案如下：

  1. 逐步输入字符串。

  2. 如果输入字符串以数字开头，则表示组合的开头。继续递归前进，其中新的输入参数是删除了匹配数字的字符串。

  3. 如果输入字符串与数字完全相等，则组合结束。

我用Python编写了您问题的解决方案。当你用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)

上述程序的输出是：

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

或者，如果您只对长度感兴趣，3

这是有效的：

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)));
    };

因此，combinations(123)将产生：

abcawlc

如果你更喜欢它作为常规方法，那么它就是：

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)));
}

一个简单的(尽管不是干净的(实现(带记忆(，仅用于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

无记忆：

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)

带记忆的版本快得多，这可以在CodeSkulptor链接中看到。在CodeSkulptor上测试。

C#中的实现可以在这里找到。NetFiddle。

解决方案基于这样一个事实，即问题涉及重叠的子问题(因此也是记忆化的候选问题(。

让我们浏览一下这里可用的基本条件：

  1. 任何长度为1的字符串都将始终产生一个组合
  2. 长度为2的字符串将产生至少一个组合(两个单独的数字都可以转换为字母表(。只有当字符串的整数值小于26(因为我们有26个字母(时，才会产生第二个组合

既然我们已经建立了基本条件，我们就可以利用它们来建立我们需要检查的案例。

字符串的组合可以有两种可能性：

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

对于给定的字符串，有两个可能的组合：一个考虑第一个数字，另一个考虑前两个数字。因此，字符串的组合数将是仅考虑第一个数字的组合数和考虑前两个数字的组合数的和。

我们确信，第一种情况总是会产生一定数量的组合，因为一个数字可以用字母表表示。然而，第二种情况只会在前两个数字组成字母表的情况下产生组合，即数字<=26。

既然我们已经列出了所有这些，我们可以继续讨论解决方案，它可以在这个DotNetFiddle和下面找到。代码和注释应该是不言自明的。

    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;
    }
相关文章：