遞歸/迭代麻煩，將單詞數組轉換成短語

Question

我試圖使用單詞列表數組來建立「短語」列表。我有一個數組，看起來是這樣的：

[ [ 'big', 'small', 'wild' ], 
    [ 'brown', 'black', 'spotted' ], 
    [ 'cat', 'dog' ] ] 

第一個數組是由此產生的「短語」的第一個字，第二陣列是第二個字，等等。單詞列表的數量是可變的，它可以是兩個單詞列表或五個列表。我有麻煩數組轉換的東西，看起來像這樣：

[ [ 'big', 'brown', 'cat' ], 
    [ 'big', 'brown', 'dog' ], 
    ... 
    [ 'wild', 'spotted', 'dog'] ] 

所得陣列的順序並不重要，但如果原數組有三個單詞列表，然後將得到的嵌套數組應該是三個字長。

我正在用Javascript寫這篇文章，但隨意使用任何你喜歡的語言，因爲遞歸概念應該基本相同。

Answer 1

如何在C＃中的實現？不幸的是，列表操作隱藏了算法。

using System.Collections.Generic; 

namespace CSharpTest 
{ 
class Program 
{ 
    static List<List<string>> BuildResult(List<List<string>> curPhrases, List<List<string>> words) 
    { 
     // Each step in the recursion removes the first list of 
     // words and creates a new list of phrases that contains 
     // all combinations of a previous phrase and a word. 

     // Remove the words to be added 
     List<string> wordsToAdd = words[0]; 
     words.RemoveAt(0); 

     // Construct the new list of phrases 
     List<List<string>> newPhrases = new List<List<string>>(); 
     foreach (string word in wordsToAdd) 
     { 
      foreach (List<string> curPhrase in curPhrases) { 
       // Create the new phrase 
       List<string> newPhrase = new List<string>(); 
       newPhrase.AddRange(curPhrase); 
       newPhrase.Add(word); 

       // Add it to the list. 
       newPhrases.Add(newPhrase); 
      } 
     } 

     if (words.Count > 0) 
     { 
      // Recurse 
      return BuildResult(newPhrases, words); 
     } 

     // No more words, so we're done. 
     return newPhrases; 
    } 

    static void Main(string[] args) 
    { 
     List<List<string>> words 
      = new List<List<string>> { 
       new List<string> { "big", "small", "wild" }, 
       new List<string> { "brown", "black", "spotted"}, 
       new List<string> { "cat", "dog" } }; 
     WriteWords(words); 

     // Initialize the recursion with an empty list 
     List<List<string> > emptyList = new List<List<string>> { new List<string>() }; 

     List<List<string>> result = BuildResult(emptyList, words); 

     WriteWords(result); 
    } 

    static void WriteWords(List<List<string>> words) 
    { 
     foreach (List<string> wordList in words) 
     { 
      foreach (string word in wordList) 
      { 
       System.Console.Write(word + " "); 
      } 
      System.Console.WriteLine(""); 
     } 
    } 
} 

}

Answer 2

在F＃它只是這個

let wordLists = [ [ "big"; "small"; "wild" ] 
        [ "brown"; "black"; "spotted" ] 
        [ "crazy"; "happy" ] 
        [ "cat"; "dog" ] ] 

let rec MakePhrase ll = [ 
    match ll with 
    | [] -> yield [] 
    | l::t -> 
     for suffix in MakePhrase t do 
     for x in l do 
     yield x :: suffix ] 

MakePhrase wordLists 
|> List.iter (printfn "%A") 

其輸出以下：

["big"; "brown"; "crazy"; "cat"] 
["small"; "brown"; "crazy"; "cat"] 
["wild"; "brown"; "crazy"; "cat"] 
["big"; "black"; "crazy"; "cat"] 
["small"; "black"; "crazy"; "cat"] 
["wild"; "black"; "crazy"; "cat"] 
["big"; "spotted"; "crazy"; "cat"] 
["small"; "spotted"; "crazy"; "cat"] 
["wild"; "spotted"; "crazy"; "cat"] 
["big"; "brown"; "happy"; "cat"] 
["small"; "brown"; "happy"; "cat"] 
["wild"; "brown"; "happy"; "cat"] 
["big"; "black"; "happy"; "cat"] 
["small"; "black"; "happy"; "cat"] 
["wild"; "black"; "happy"; "cat"] 
["big"; "spotted"; "happy"; "cat"] 
["small"; "spotted"; "happy"; "cat"] 
["wild"; "spotted"; "happy"; "cat"] 
["big"; "brown"; "crazy"; "dog"] 
["small"; "brown"; "crazy"; "dog"] 
["wild"; "brown"; "crazy"; "dog"] 
["big"; "black"; "crazy"; "dog"] 
["small"; "black"; "crazy"; "dog"] 
["wild"; "black"; "crazy"; "dog"] 
["big"; "spotted"; "crazy"; "dog"] 
["small"; "spotted"; "crazy"; "dog"] 
["wild"; "spotted"; "crazy"; "dog"] 
["big"; "brown"; "happy"; "dog"] 
["small"; "brown"; "happy"; "dog"] 
["wild"; "brown"; "happy"; "dog"] 
["big"; "black"; "happy"; "dog"] 
["small"; "black"; "happy"; "dog"] 
["wild"; "black"; "happy"; "dog"] 
["big"; "spotted"; "happy"; "dog"] 
["small"; "spotted"; "happy"; "dog"] 
["wild"; "spotted"; "happy"; "dog"]