Finding a Cartesian product of multiple lists

I came up with an extension method to find a Cartesian product of multiple IEnumerable sets. I was able to achieve lazy enumeration via yield return, but I didn't think of a way to do it non-recursively. The result ended up being a recursive lazy enumeration iterator method, the first of its kind! At least as far as I've ever written.

The idea of the problem came from a Stack Overflow question where a guy had many sets of characters, and wanted to generate a combination of all of them. Now I'm just interested because it's a fun problem!

I'd appreciate any kind of review, although here's two specific things I'm most interested in:

• Can this algorithm can be de-recursed? If so - should it be, and how?

• Is there some way it could be generalized even more, beyond what I've done?

```
public static class MultiCartesianExtension
{
public static IEnumerable MultiCartesian(this IEnumerable> input)
{
return input.MultiCartesian(x => x);
}

public static IEnumerable MultiCartesian(this IEnumerable> input, Func selector)
{
// Materializing here to avoid multiple enumerations.
var inputList = input.ToList();
var buffer = new TInput[inputList.Count];
var results = MultiCartesianInner(inputList, buffer, 0);
var transformed = results.Select(selector);
return transformed;
}

private static IEnumerable MultiCartesianInner(IList> input, TInput[] buffer, int depth)
{
foreach (var current in input[depth])
{
buffer[depth] = current;
if (depth == buffer.Length - 1)
{
// This is to ensure usage safety - the original buffer
// needs to remain unmodified to ensure a correct sequence.
var bufferCopy = (TInput[])buffer.Clone();
yield return bufferCopy;
}
else
{
// Funky recursion here
foreach (var a in MultiCartesia

You can indeed create a cartesian product without recursion. What you need is to use the enumerator.

I used a non-generic enumerator to work with any types.

public static IEnumerable Cartesian(this IEnumerable items)
{
    var slots = items
       // initialize enumerators
       .Select(x => x.GetEnumerator())
       // get only those that could start in case there is an empty collection
       .Where(x => x.MoveNext())
       .ToArray();

    while (true)
    {
        // yield current values
        yield return slots.Select(x => x.Current);

        // increase enumerators
        foreach (var slot in slots)
        {
            // reset the slot if it couldn't move next
            if (!slot.MoveNext())
            {
                // stop when the last enumerator resets
                if (slot == slots.Last()) { yield break; }
                slot.Reset();
                slot.MoveNext();
                // move to the next enumerator if this reseted
                continue;
            }
            // we could increase the current enumerator without reset so stop here
            break;
        }
    }
}

Example:

var letters = new string[] { "A", "B" };
var numbers = new[] { 1, 2, 3 };
var symbols = new[] { "@", "#" };
var empty = new string[] { };

var collections = new IEnumerable[] { letters, numbers, symbols, empty };
collections.Cartesian()
    // this is just for show
   .Select(x => string.Join("", x.Cast()))
   .OrderBy(x => x)
   .Dump(); // linqpad

result:

A1# 
A1@ 
A2# 
A2@ 
A3# 
A3@ 
B1# 
B1@ 
B2# 
B2@ 
B3# 
B3@

StackExchange Code Review Q#122699, answer score: 4