List> unique permutations using LINQ

Question

I need an algorithm that will take any number of List inside a List and generate a unique set of permutations. I prefer to find a LINQ solution.

I actually have a Javascript function that works well and I'm trying to recreate it in C# (see code at bottom)

C# (my attempt) - Visual Studio does not like my second Aggregate(). It says the arguments cannot be inferred from usage

public static void testit()
{
    List<List<string>> master = new List<List<string>>();

    List<string> voltages = new string[] { "208", "230", "460" }.ToList();
    List<string> sysConfigs = new string[] { "10205", "10210", "10215", "10220" }.ToList();

    master.Add(voltages);
    master.Add(sysConfigs);

    var amp = master.Aggregate(
            (a, b) => a.Aggregate(
                (r, v) => r.Concat(
                    b.Select(w => new List<string>().Concat(v, w))
                ), new List<string>()
            )
    ); 
}

The output of this new collection should look like this:

/*
   OUTPUT (displayed as arrays - but will be lists):
   [
     ["208", "10205"],
     ["208", "10210"],
     ["208", "10215"],
     ["208", "10220"],
     ["230", "10205"],
     ["230", "10210"],
     ["230", "10215"],
     ["230", "10220"],
     ["460", "10205"],
     ["460", "10210"],
     ["460", "10215"],
     ["460", "10220"]
   ];

Here's a Javascript function that works well that I'm trying to mimic in C#:

function getPermutations(arr) {
   return arr.reduce(
       (a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), [])
   );

}

var voltages = ["208", "230", "460"];
var sysConfigs = ["10205", "10210", "10215", "10220"];

var master = [];
master.push(voltages);
master.push(sysConfigs);

var newArr = getPermutations(master);
console.log(newArr);

Type inference can't happen on return types, which is what your outermost `Aggregate` would need to know from the innermost `Aggregate`. You'll probably have to explicitly type your lambdas. — Kenneth K., May 31 '18 at 20:22
You are passing two parameters to the inner `Aggregate` - a lambda and a `List`. That does not match any [signature of `Aggregate`](https://msdn.microsoft.com/en-US/library/system.linq.enumerable.aggregate(v=vs.110).aspx). You cannot really take function names and signatures from one language and expect them to exist in another language, with same meaning and order. — GSerg, May 31 '18 at 20:36
@GSerg I understand languages do not mix - the point of showing the Javascript function was purely for method. But your point about signatures of Aggregate seems to imply that this can't be done. If so, is there maybe a recursive function that might work? — bagofmilk, May 31 '18 at 20:44
No, my point is that you need to pass the parameters in the order the C# signatures expect them. — GSerg, May 31 '18 at 20:45
I see. I did notice that hovering over `r` and `v` Visual Studio did not recognize their type - so I defined them as strings. When I did that, all types were recognized yet I received the same error. — bagofmilk, May 31 '18 at 20:47
No you did not. You are passing the `seed` last. It must go first. — GSerg, May 31 '18 at 20:48
@Chris thanks for the shout-out; https://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/ is a better link. — Eric Lippert, May 31 '18 at 21:18
@EricLippert: Ah, ok. I remembered that you wrote that article (and all your articles that I've read are brilliant - brief fanboying there) and just googled and went for the first hit. Now your comment is here with the better link I'll delete my original. — Chris, May 31 '18 at 21:22

Eric Lippert · Accepted Answer · 2018-05-31T21:20:34.553

As noted in other questions, this is the Cartesian product, not a permutation.

Short version: Just go to my blog:

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

Long version:

Cartesian product of two lists is built-in in C# in the form of SelectMany or a query comprehension. Let's start with that.

Before we get into that though, please do not ever do this:

List<string> voltages = new string[] { "208", "230", "460" }.ToList()

Either do this:

IEnumerable<string> voltages = new string[] { "208", "230", "460" };

Or do this:

List<string> voltages = new List<string>() { "208", "230", "460" };

But do not make an array and then to-list it! Just make a list from the beginning.

OK, onward. We have two sequences:

IEnumerable<string> voltages = new string[] { "208", "230", "460" };
IEnumerable<string> sysConfigs = new string[] { "10205", "10210", "10215", "10220" };

We want their Cartesian product:

IEnumerable<IEnumerable<string>> master = 
  from v in voltages
  from s in sysConfigs
  select new List<string>() { v, s };

And we're done.

If you don't like "comprehension form" then you can use "fluent form":

IEnumerable<IEnumerable<string>> master = 
  voltages.SelectMany(
    v => sysConfigs, 
    (s, v) => new List<string>() { v, s });

If you want a list of lists:

List<List<string>> master = 
  voltages.SelectMany(
    v => sysConfigs, 
    (v, s) => new List<string>() { v, s })
  .ToList();

Easy peasy.

The meaning of this operation should be clear, but if it is not: the general form is:

var zs = 
  from x in xs
  from y in f(x) // f takes x and returns a collection of ys
  g(x, y)        // do something with every combination of x and y to make a z

In your case, f(x) is just "always produce the second collection", but it need not be; the collection could depend on x. The result is a sequence of z.

Now, what you need is the Cartesian product of arbitrarily many sequences.

Your intuition that this is an aggregation of concatenations is correct. We can solve it like this:

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

Notice how this combines the three operations: a select-many query, a concatenation, and an aggregation. Study this carefully to see how it works.

@bagofmilk: Because the language already has a syntax for creating a list directly. It's weird to create a collection that is not a list and then create a list from it, when you can just create the list in the first place. — Eric Lippert, Jun 01 '18 at 01:35

Andrzej Gis · Answer 2 · 2018-05-31T21:57:08.717

1

This is the correct version of your code

var amp = master.Aggregate(
    new List<List<string>>(){new List<string>()},
    (a, b) => a.Aggregate(
        new List<List<string>>(new List<List<string>>()),
        (r, v) => r.Concat(
            b.Select(w => v.Concat(new List<string>{w}).ToList())
        ).ToList()));

edited May 31 '18 at 21:57

answered May 31 '18 at 20:31

Andrzej Gis

13,706
14
86
130

List> unique permutations using LINQ

2 Answers2