查找字母組合的數量，使每個字母等於一個數字

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