查找字母组合的数量，使每个字母等于一个数字

Question

我试图找出以下使用C＃： 具有a = 1，b = 2，c = 3等到z的算法。当给定一串数字时，我需要计算字母数组合。因为'1'+'2'+'3'= abc，'1'+ 23'= aw，'12'+'3'='123'，所以输出将为。 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; 
    } 

我知道有逻辑错误。每个呼叫中​​组合列表都会重置。而组合创建的方式缺少一个我无法获得的调整。我不期望写出整个代码。有用的提示将不胜感激。

Answer 1

的解决方案如下：

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') 

...或者，如果你只是在长度感兴趣，

Answer 2

这工作：

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)随后将产生：

 
abc 
aw 
lc 

如果你宁愿它作为常规方法则是这样的：

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

Answer 3

一个简单（虽然不干净），实现（与记忆化）只对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 link中可以看到。 在CodeSkulptor here上测试。

在C＃中的实现可以在this .NetFiddle中找到。

---

该解决方案基于这样的事实，即问题涉及重叠子问题（因此也是备忘录的候选人）。

让我们通过这里提供的基本条件：

1. 长度为1的任意字符串总是产生一个组合。
2. 长度为2的字符串将产生至少一个组合（两个单独的数字都可以转换为字母表）。如果字符串的整数值小于等于26（因为我们有26个字母表）

现在，我们已经建立了基础条件下，我们可以使用它们来建立的情况下的第二组合将只产生我们需要检查。

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

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

对于一个给定的字符串，有2个可能的组合：其中，一个第一数字被认为是与第二，其中第一两个数字被考虑。因此，组合的一个字符串的数目将是考虑仅第一个数字和考虑前两位组合数量的组合数的总和。

我们知道第一种情况总会产生一定数量的组合，因为一个数字可以表示为一个字母表。但是，如果的前两位数字组成字母表，那么第二种情况只会产生组合，即< = 26。

现在，我们已经奠定了这一切下来，我们就可以移动到该解决方案，它可以在this 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; 
    }