如何使用遞歸獲取設定順序中的每個字符串組合？

Question

這一問題與我先前的問題，在這裏問：

How do I get every combination of letters using yield return and recursion?

我有一個像這樣的字符串的若干名單，從幾十的可能名單：

1: { "A", "B", "C" } 
2: { "1", "2", "3" } 
3: { "D", "E", "F" } 

這三者是隻是作爲一個例子，用戶可以從數十個類似的列表中選擇不同數量的元素。另一個例子，這也是一個用戶一個完全有效的選擇：

25: { } // empty 
4: { "%", "!", "$", "@" } 
16: { "I", "a", "b", "Y" } 
8: { ")", "z", "!", "8" } 

我想要做的就是串可能的每個組合，同時保持名單的「秩序」。換句話說，假設我們正在查看第一個列表，那麼第一個組合將是A1D，然後是A1E，然後是A1F，然後是B1D，然後是B1E，依此類推。根據我以前問的問題提供了答案，我寫了這方面的工作遞歸算法：

public void Tester() 
{ 
    var collection = new List { list1, list2, list3 }; 
    var answer = GetStringCombinations(collection).ToList(); 

    answer.ForEach(Console.WriteLine); 
} 

private IEnumerable<string> GetStringCombinations(List<List<string>> collection) 
{ 
    // if the collection is empty, return null to stop the recursion 
    if (!collection.Any()) 
    { 
     yield return null; 
    } 
    // recurse down the list, selecting one letter each time 
    else 
    { 
     foreach (var letter in collection.First()) 
     { 
      // get the collection sans the first item 
      var nextCollection = collection.Skip(1).ToList(); 

      // construct the strings using yield return and recursion 
      foreach (var tail in GetStringCombinations(nextCollection)) 
      { 
       yield return letter + tail; 
      } 
     } 
    } 
} 

然而，這種代碼依賴於yield return正常工作。你如何在不使用關鍵字yield return的情況下實現該算法，例如，如果我將代碼移植到ColdFusion或Ruby（假設它們沒有類似的關鍵字）？

Answer 1

我沒有測試，但應該工作

private List<string> GetStringCombinations(List<List<string>> collection) 
{ 
List<string> ls = new List<string>(); 

// if the collection is empty, return null to stop the recursion 
if (!collection.Any()) 
{ 
    return null; 
} 
// recurse down the list, selecting one letter each time 
else 
{ 
    foreach (var letter in collection.First()) 
    { 
     // get the collection sans the first item 
     var nextCollection = collection.Skip(1).ToList(); 

     // construct the strings using yield return and recursion 
     foreach (var tail in GetStringCombinations(nextCollection)) 
     { 
      ls.add(letter + tail); 
     } 
    } 
} 
return ls; 

}

Answer 2

僞代碼：

Combinations(lists[1..n], start, prefix) 
    1. If start = n + 1 then print(prefix) 
    2. else then 
    3. for i = 1 to lists[start].length do 
    4.  Combinations(lists, start + 1, 
       prefix.append(lists[start][i]) 

類似的東西應該工作。爲了獲得最佳結果，請使用start =最低數組索引和prefix =空字符串來調用上述內容。隨着一些調整，這將很好。