Cartesian Product in C# using enumeratos

Question

I'm trying to implement one of the solutions found in the question C# Permutation of an array of arraylists? It should perform the the cartesian product, but instead it returns the right number of lists, but each list is always the just the first of each array. The code and results are below.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace TestCartProd
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            string[][] myList = new string[3][];
            myList[0] = new string[] { "1", "5", "3", "9" };
            myList[1] = new string[] { "2", "3" };
            myList[2] = new string[] { "a", "93" };

            List<IEnumerable<string>> v = GetPermutations (myList).ToList();

            foreach (IEnumerable t in v) {
                foreach (string u in t) {
                    Console.Write (u);
                }
                Console.WriteLine ();
            }

        }

        public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<IEnumerable<T>> lists)
        {
            // Check against an empty list.
            if (!lists.Any())
            {
                yield break;
            }

            // Create a list of iterators into each of the sub-lists.
            List<IEnumerator<T>> iterators = new List<IEnumerator<T>>();
            foreach (var list in lists)
            {
                var it = list.GetEnumerator();
                // Ensure empty sub-lists are excluded.
                if (!it.MoveNext())
                {
                    continue;
                }
                iterators.Add(it);
            }

            bool done = false;
            while (!done)
            {
                // Return the current state of all the iterator, this permutation.
                yield return from it in iterators select it.Current;

                // Move to the next permutation.
                bool recurse = false;
                var mainIt = iterators.GetEnumerator();
                mainIt.MoveNext(); // Move to the first, succeeds; the main list is not empty.
                do
                {
                    recurse = false;
                    var subIt = mainIt.Current;
                    if (!subIt.MoveNext())
                    {
                        subIt.Reset(); // Note the sub-list must be a reset-able IEnumerable!
                        subIt.MoveNext(); // Move to the first, succeeds; each sub-list is not empty.

                        if (!mainIt.MoveNext())
                        {
                            done = true;
                        }
                        else
                        {
                            recurse = true;
                        }
                    }
                }
                while (recurse);
            }
        }
    }
}

Results: 12a 12a 12a 12a 12a 12a 12a 12a 12a 12a 12a 12a 12a 12a 12a 12a

Answer 1

The problem in your code

the it in it.Current will always be newly created (by the LINQ statement: from it in iterators) and so of course will always return the first elements

LINQ solution

at first I would not look to much at performance and implement the algorithm using simple LINQ/recursion - below is an example (where I obviously used some list-like terms with enumerables and did not care about performance, stack-usage,... at all):

public static IEnumerable<T> Empty<T>()
{
    return new T[] {};
}

public static IEnumerable<T> Cons<T>(T head, IEnumerable<T> tail)
{
    yield return head;
    foreach (var t in tail)
        yield return t;
}
public static IEnumerable<IEnumerable<T>> Crossproduct<T>(IEnumerable<IEnumerable<T>> sets)
{
    if (!sets.Any())
        return new[] {Empty<T>()};

    var head = sets.First();
    var tailCross = Crossproduct<T>(sets.Skip(1));

    return
        from h in head
        from ts in tailCross
        select Cons(h, ts);
}

from here you can begin to translate it back in loops if you wish but as you saw in your example it's not that easy.

remarks

as you see I did not fix your code (you should be able to do this yourself using the debugger) but as you did ask no question at all this might be of interest or not.

example-output

using your provided example and output-loop with this code:

string[][] myList = new string[3][];
myList[0] = new string[] { "1", "5", "3", "9" };
myList[1] = new string[] { "2", "3" };
myList[2] = new string[] { "a", "93" };

var crossP = Crossproduct(myList);

foreach (var t in crossP)
{
    foreach (string u in t)
    {
        Console.Write(u);
    }
    Console.WriteLine();
}

produces this (I think it is what you want):

12a
1293
13a
1393
52a
5293
53a
5393
32a
3293
33a
3393
92a
9293
93a
9393

Answer 2

@Carsten has provided a clean code you may try. Though if you want to fix your code, you may try projecting the yield return as shown below:

 while (!done)
            {
                // Return the current state of all the iterator, this permutation.
                yield return iterators.Select(it => it.Current).ToArray();
                //Notice Select(...).ToArray() above.

Answer 3

Another Linq solution I have used in the past is to use the Aggregate extension.

Start our accumulator off as the empty product, and every time through the loop we add to it by combining the current sequence with the product so far. At every iteration the accumulator will be the Cartesian product of all the sequences seen so far.

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
{
  IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
  return sequences.Aggregate(
    emptyProduct,
    (accumulator, sequence) =>
      from accseq in accumulator
      from item in sequence
      select accseq.Concat(new[] {item}));
}

Code Snippet Source