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:

  1. Can this algorithm can be de-recursed? If so - should it be, and how?
  2. Is there some way it could be generalized even more, beyond what I've done?

public static class MultiCartesianExtension
    public static IEnumerable<TInput[]> MultiCartesian<TInput>(this IEnumerable<IEnumerable<TInput>> input)
        return input.MultiCartesian(x => x);

    public static IEnumerable<TOutput> MultiCartesian<TInput, TOutput>(this IEnumerable<IEnumerable<TInput>> input, Func<TInput[], TOutput> 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<TInput[]> MultiCartesianInner<TInput>(IList<IEnumerable<TInput>> 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;
                // Funky recursion here
                foreach (var a in MultiCartesianInner(input, buffer, depth + 1))
                    yield return a;


var input = new string[]

foreach (var result in input.MultiCartesian(x => new string(x)))

// Results:
// A1@
// A1#
// A2@
// A2#
// A3@
// A3#
// B1@
// B1#
// B2@
// B2#
// B3@
// B3#
  • 2
    \$\begingroup\$ Possible bug - IEnumerable doesn't guarantee ordering, so you can't count on "a correct sequence". Consider var input = new HashSet<string> {"AB", "123", "@#"}; \$\endgroup\$
    – Comintern
    Commented Mar 13, 2016 at 1:21
  • 1
    \$\begingroup\$ @Comintern Good catch! Although I'd argue that it should be up to the caller to ensure this doesn't happen. If the order doesn't matter - it's fine to use a HashSet. If it does matter - it's up to the caller to provide an ordered collection. \$\endgroup\$ Commented Mar 13, 2016 at 14:24
  • \$\begingroup\$ Wouldn't the a cartesian product of these sets also include results like 1A@ \$\endgroup\$
    – jkdba
    Commented Mar 13, 2016 at 17:42
  • \$\begingroup\$ @JohnK No, a Cartesian product consists of only combinations. Take a look at this image. Finding the permutations would be very easy one you have the combinations though, with the MoreLinq's Permutations method. \$\endgroup\$ Commented Mar 15, 2016 at 2:22
  • \$\begingroup\$ @GediminasMasaitis The link to Wikimedia Commons you provided is prone to rusting – the part /4/4e/ refers to some Commons' internal indices, which are rebuilt from time to time. It's safer to use a stable links to a resource instead, like https://commons.wikimedia.org/wiki/File:Cartesian_Product_qtl1.svg. \$\endgroup\$
    – CiaPan
    Commented Jan 24, 2018 at 7:43

2 Answers 2


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

    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; }
                // move to the next enumerator if this reseted
            // we could increase the current enumerator without reset so stop here


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 };
    // this is just for show
   .Select(x => string.Join("", x.Cast<object>()))
   .OrderBy(x => x)
   .Dump(); // linqpad


  • \$\begingroup\$ It could be even shorter :) \$\endgroup\$ Commented Sep 3, 2016 at 22:38
  • 1
    \$\begingroup\$ I think the code is missing the Dispose() of the enumerators (slots[i]). To be "fully correct" I would then need to be careful about exceptions... \$\endgroup\$
    – Pablo H
    Commented Aug 3, 2017 at 23:55
  • \$\begingroup\$ collections.Cartesian() // this is just for show .Select This will never execute as we can not apply extension methods on IEnumerable. It should be IEnumerable<T>. Need to Cast it in object[].. collections.GetCartesian().Cast<object[]>() // this is just for show .Select(x => string.Join("", x.Cast<object>())) .OrderBy(x => x); \$\endgroup\$
    – manoj jain
    Commented Jan 9, 2018 at 17:34

Found this one from a number of years back. Seems short and to the point:

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
    if (sequences == null)
        return null;

    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };

    return sequences.Aggregate(
        (accumulator, sequence) => accumulator.SelectMany(
            accseq => sequence,
            (accseq, item) => accseq.Concat(new[] { item })));

Not the answer you're looking for? Browse other questions tagged or ask your own question.