Recursion/iteration troubles, transforming an array of words into phrases

Question

I'm trying to build a list of "phrases" using an array of word lists. I have an array that looks something like this:

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

The first array is the first word in the resulting "phrase", the second array is the second word, and so on. The number of word lists is variable, it can be two lists of words or five lists. I'm having trouble converting that array to something that looks like this:

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

The order of the resulting array doesn't matter, but if the original array has three word lists, then the resulting nested arrays should be three words long.

I'm writing this in Javascript, but feel free to use whatever language you prefer as the recursion concept should be basically the same.

Answer 1

How about an implementation in C#? Unfortunately, the list manipulation hides the algorithm a bit.

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

In F# it is just this

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

which prints the following output:

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