3
\$\begingroup\$

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;
            }
            else
            {
                // Funky recursion here
                foreach (var a in MultiCartesianInner(input, buffer, depth + 1))
                {
                    yield return a;
                }
            }
        }
    }
}

Usage:

var input = new string[]
{
    "AB",
    "123",
    "@#",
};

foreach (var result in input.MultiCartesian(x => new string(x)))
{
    Console.WriteLine(result);
}

// Results:
// A1@
// A1#
// A2@
// A2#
// A3@
// A3#
// B1@
// B1#
// B2@
// B2#
// B3@
// B3#
\$\endgroup\$
  • 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 Mar 13 '16 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\$ – Gediminas Masaitis Mar 13 '16 at 14:24
  • \$\begingroup\$ Wouldn't the a cartesian product of these sets also include results like 1A@ \$\endgroup\$ – jkdba Mar 13 '16 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\$ – Gediminas Masaitis Mar 15 '16 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 Jan 24 '18 at 7:43
3
\$\begingroup\$

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())
       .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<object>()))
   .OrderBy(x => x)
   .Dump(); // linqpad

result:

A1# 
A1@ 
A2# 
A2@ 
A3# 
A3@ 
B1# 
B1@ 
B2# 
B2@ 
B3# 
B3@
\$\endgroup\$
  • \$\begingroup\$ It could be even shorter :) \$\endgroup\$ – Dmitry Nogin Sep 3 '16 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 Aug 3 '17 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 Jan 9 '18 at 17:34
1
\$\begingroup\$

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(
        emptyProduct,
        (accumulator, sequence) => accumulator.SelectMany(
            accseq => sequence,
            (accseq, item) => accseq.Concat(new[] { item })));
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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