CODEWITHSUNDEEP
c#linqcartesian-product
Kim Smith
Kim Smith

Reputation: 145

How to get a Cartesian product of a list containing lists?

I am able to get a cartesian product of hard coded / known list as below using Linq in C#. But I need to get a cartesion product of a list which itself contains a list of elements. Can some one help with the Linq query to use? Please see the below. In the first part I am getting the cartesian product fine, but how do I replicate the behavior using a List of list?

static void Main(string[] args)
        {
            int[] list1 = { 11, 12, 13};
            int[] list2 = { 21, 22, 23 };
            int[] list3 = { 31, 32, 33 };

            Console.Write("\nLINQ : Generate a Cartesian Product of three sets : ");
            Console.Write("\n----------------------------------------------------\n");

            var cartesianProduct = from n1 in list1
                                   from n2 in list2
                                   from n3 in list3
                                   select new { n1, n2, n3};

            Console.Write("The Cartesian Product are : \n");
            foreach (var ProductList in cartesianProduct)
            {
                Console.WriteLine(ProductList);
            }

            // The above code works; now I want the same results but by using a list containing lists.

            List<long> List1 = new List<long>();
            List1.Add(11);
            List1.Add(12);
            List1.Add(13);

            List<long> List2 = new List<long>();
            List2.Add(21);
            List2.Add(22);
            List2.Add(23);

            List<long> List3 = new List<long>();
            List3.Add(31);
            List3.Add(32);
            List3.Add(33);

            List<List<long>> bigList = new List<List<long>>();
            bigList.Add(List1);
            bigList.Add(List2);
            bigList.Add(List3);

            // How to get the cartesian product of a bigList that may contain multiple lists in Linq?


            Console.ReadLine();
        }

Upvotes: 0

Views: 1195

Answers (1)

NetMage
NetMage

Reputation: 26917

Here is a LINQ extension method using Aggregate:

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) =>
    sequences.Aggregate(
        Enumerable.Empty<T>().AsSingleton(),
        (accumulator, sequence) => accumulator.SelectMany(
            accseq => sequence,
            (accseq, item) => accseq.Append(item)));

You need the extension method AsSingleton:

public static IEnumerable<T> AsSingleton<T>(this T item) => new[] { item };

This is based on this answer from @EricLippert.

Upvotes: 1

Related Questions