递归/迭代麻烦，将单词数组转换为短语

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"]