How to combine multiple lists of same or different lengths in Linq?

Question

I would like to build a method or extension method that takes multiple lists and combines them in the following way:

Lets say i have two lists:

        int[] list1 =  {3, 1, 2};
        int[] list2 =  {5, 4 };

I would expect a list of arrays as a result like this:

[1,4]
[1,5]
[2,4]
[2,5]
[3,4]
[3,5]

The number of columns in my resulting list of arrays would be determined by the amount of lists passed and both columns need to be sorted. The number of rows is just the (length of list A) * (length of list B) * (length of list N)

In this example is 3 * 2 = 6 rows. 2 columns (because 2 input lists).

What would be an elegant way of doing this with linq?

Thanks!

Have you even tried solving this with normal loops and natural algorithm first? I would never use `LINQ` for such a complicated problem. Even when `LINQ` can do that for you, it would be less efficient and more `hard-to-understand` than the normal loops. **LINQ should not be used at any cost**. — King King, Oct 22 '13 at 17:00
I agree that LINQ may be harder to understand and less efficient some times, but I want to learn more about it. I thought about solving this with normal loops but was curious about the LINQ way. My application won't be dealing with enormous lists so I think performance shouldn't be an issue. — Adolfo Perez, Oct 22 '13 at 17:09
@KingKing: This is a perfectly reasonable problem to solve with LINQ and is not complicated in the least. The 2-ary Cartesian product is in fact the *foundational* LINQ sequence operation, `SelectMany`. All LINQ operators can be built out of `SelectMany`; it is the bind operation of the sequence monad. The n-ary Cartesian product is a bit more complicated of course. — Eric Lippert, Oct 23 '13 at 16:33
@EricLippert thanks, maybe you're too familiar with `LINQ`, to me, sometimes I still feel it's easier to think out the solution with traditional loops (and separate methods) than using `LINQ`, however I still always use `LINQ` as partially as possible (not kind of `one-line LINQ`). — King King, Oct 23 '13 at 16:42
@EricLippert if you post my answer as you I'll be happy to accept yours. I don't want to accept my own answer when credit goes to you. Thanks! — Adolfo Perez, Oct 24 '13 at 13:20

score 3 · Answer 1 · answered Oct 22 '13 at 15:36

3

Try cross join

int[] list1 =  {3, 1, 2};
int[] list2 =  {5, 4 }; 

var result = (from l1 in list1
             from l2 in list2
             select new [] {l1, l2}).ToList()

answered Oct 22 '13 at 15:36

Tilak

30,108
19
83
131

1

How can I adapt this into a method that can take n amount of lists? – Adolfo Perez Oct 22 '13 at 15:46

score 2 · Answer 2 · answered Oct 22 '13 at 15:36

2

Use SelectMany:

var combinations = list1.SelectMany(i1 => list2.Select(i2 => new[] { i1, i2 }));

or if you prefer

var combinations = list1.SelectMany(i1 => list2, (i1, i2) => new[] { i1, i2 });

If you want to get the results in a specific order you can follow this up with OrderBy etc.

answered Oct 22 '13 at 15:36

Jon

428,835
81
738
806

But what if I send more than 2 lists? I would like to have a method that can take n amount of lists. – Adolfo Perez Oct 22 '13 at 15:46
1

@AdolfoPerez: That would be more complicated. See http://stackoverflow.com/questions/4073713/is-there-a-good-linq-way-to-do-a-cartesian-product – Jon Oct 22 '13 at 15:54

Adolfo Perez · Answer 3 · 2013-10-24T13:46:51.100

Credit goes here to @Jon for pointing me to the right source and @EricLippert for his clever solution:

    public 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 }));
    }

http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/

Works nice with ints and strings:

        string[] list1 =  {"1", "2", "3"};
        string[] list2 =  { "4","5" };

        var lists = new List<string[]>(){list1,list2};

        var result = lists.CartesianProduct();

How to combine multiple lists of same or different lengths in Linq?

3 Answers3

Linked