How do I get every combination of strings in a set order using recursion?

This question is related to my earlier question, asked here:

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

I have several lists of strings like so, from a possible list of several dozen:

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

These three were only picked as an example, and the user can pick from several dozen similar lists with varying number of elements. For another example, this is also a perfectly valid selection for a user:

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

What I want to do is get every combination of strings possible while keeping the 'order' of the lists. In other words, assuming we're looking at the first list, the first combination will be A1D, then A1E, then A1F, then B1D, then B1E, and so on and so forth. Based on the answer pr开发者_运维问答ovided in my previously-asked question, I've written this working recursive algorithm:

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

However, this code depends on yield return to work properly. How would you implement this algorithm without the use of the yield return keyword, for example if I were to port the code to ColdFusion or Ruby (assuming that they don't have a similar keyword either)?

---

I am not tested it, but should work

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;

}

---

Pseudocode:

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

Something like that should work. For best results, call the above with start = the lowest array index and prefix = the empty string. With some tweaking, this will work nice.