Finding combinations of a grouped list using LINQ in c#

Question

Lets say I have an object which contains a persons name, and their city of origin.

public class personDetails
{
    public string City;
    public string Name;
}

And I have a List with the following entries added.

Name   City
John | London
Jane | London
Tom  | New York
Bob  | New York
Fred | New York

What I'm looking for is all possible combinations of names, grouped by city.

John Tom
John Bob  
John Fred
Jane Tom
Jane Bob
Jane Fred

I can do this if I know in advance the number of groups, by using the following code

List<personDetails> personList = new List<personDetails>();
//populate list

var groupedPersons = personList.GroupBy(c => c.City);
foreach (var item1 in groupedPersons[0])
{
    foreach (var item2 in groupedPersons[1])
    {
        Console.WriteLine(item1.Name + " " + item2.Name);
    }          
}

However, this only works if i know the number of groups in advance, and quickly becomes unwieldy as the amount of groups grow larger. I'm sure that there is an elegant way to do this using LINQ, can anybody shed some light?

Take a look at this answer http://stackoverflow.com/questions/9168269/permutation-algorithms-in-c-sharp. You could join your list with itself. — Brad, May 30 '12 at 20:02
@Brad That would work for the listed example with 2 cities. What the OP wants is an N dimensional cross product, where N isn't known until runtime. That code snippet doesn't provide it. — Servy, May 30 '12 at 20:15

Servy · Accepted Answer · 2012-05-30T20:12:29.040

We'll start with the following snippet of code taken verbatum from here. (It's a good link, worth reading).

public static class MyExtensions
{
    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 }));
    }
}

After that all we need to do is:

var groupedPersons = personList.GroupBy(c => c.City)
    //need an enumerable of enumerables, not an enumerable of groupings, 
    //because the method isn't covariant.
    .Select(group => group.AsEnumerable());

var results = groupedPersons.CartesianProduct();
foreach (var group in results)
{
    foreach (var person in group)
    {
        Console.Write(person.Name + " ");
    }
    System.Console.WriteLine();
}

Okay, tested it after entering the data you provided and it prints the expected results. — Servy, May 30 '12 at 20:14
Fantastic, that works great. And a very interesting link to boot, many thanks. — John, May 30 '12 at 20:22

Finding combinations of a grouped list using LINQ in c#

1 Answers1