Linq invert a parent child sequence

Question

I have a sequence of objects like this

A1 - B1, B2, B3
A2 - B1
A3 - B1, B2

(A's are parent and contain a collection of B child objects)

I want to invert this so that the child objects (B) become the parent, i.e.

B1 - A1, A2, A3
B2 - A1, A3
B3 - A1

Anyone know the correct linq query to get this result?

horgh · Accepted Answer · 2013-02-13T00:15:23.673

At first you can do this with your own hands easily without linq:

//init original dictionary
var dict = new Dictionary<string, List<string>>
{
    {"A1",new List<string> { "B1", "B2", "B3" }},
    {"A2",new List<string> { "B1" }},
    {"A3",new List<string> { "B1", "B2"}},
};
//do the task
var newdict = new Dictionary<string, List<string>>();
foreach (var p in dict)
{
    foreach (string s in p.Value)
    {
        if (!newdict.ContainsKey(s))
            newdict[s] = new List<string>();
        newdict[s].Add(p.Key);
    }
}
//see what we've got
foreach (var p in newdict)
{
    Console.WriteLine(p.Key);
    foreach (string s in p.Value)
    {
        Console.Write(s + "\t");
    }
    Console.WriteLine();
}
Console.ReadLine();

Secondly, linq can also do the job:

var result = dict.SelectMany(p => p.Value
                                   .Select(s => new
                                   {
                                       Key = p.Key,
                                       Value = s
                                   }))
                    .GroupBy(a => a.Value)
                    .ToDictionary(g => g.Key,
                                  g => g.Select(a => a.Key)
                                        .ToList());

where I

use SelectMany to get the sequence of anonymous objects, representing pairs of key and each value from the original value List<string>
use GroupBy to actually invert the list and get the sequense of pairs, grouped by values, not keys
use ToDictionary to create the same structure as original, i.e. Dictionary<string,List<string>>.

P.S.:

Anyone know the correct linq query to get this result?

I guess noone knows, but many can make it up - this is what you've got to do in the first place, that is try to.

Ok, I should have posted what I had but wasn't working. The part I was missing was the .Select within the SelectMany. Thanks. — user380689, Feb 13 '13 at 00:29
@user380689 try reading [Writing the perfect question](http://msmvps.com/blogs/jon_skeet/archive/2010/08/29/writing-the-perfect-question.aspx) by Jon Skeet. This article indeed points all the things to remember, when writing a question on a site like SO. Following all those advices may help avoid misunderstanding in future. I'm glad my answer helped you.. — horgh, Feb 13 '13 at 00:40
You might consider using ToLookup instead of ToDictionary when the problem domain requires a multi-valued dictionary. — Eric Lippert, Feb 13 '13 at 01:38
@EricLippert I wasn't sure, if the target data sequence was meant to be easily modifiable. So as soon as `ILookup` does not provide any method to modify it, I decided to use a more general `Dictionary>`. Well, I ought to mention that in my answer. Thank you a lot for that. — horgh, Feb 13 '13 at 01:59

score 0 · Answer 2 · answered Feb 13 '13 at 03:39

Anyone know the correct linq query to get this result?

The LINQ is fairly straight forward and closely follows @Konstantin's answer...

var dict = new Dictionary<string, List<string>>
{
    {"A1",new List<string> { "B1", "B2", "B3" }},
    {"A2",new List<string> { "B1" }},
    {"A3",new List<string> { "B1", "B2"}},
};

IEnumerable<IGrouping<string,string>> inverted =
    from kvp in dict
    from child in kvp.Value
    group kvp.Key by child;

The IGrouping<string,string> has a string Key property corresponding to the unique child from the dict. The IGrouping<string,string> is IEnumerable<string> which in this case is the parents requested. In other words, this IGrouping is a lot like the original Dictionary<string,List<string>> we started with. Interestingly, a select clause is unnecessary because the language spec permits a query to end with a group-by.

Additionally, if a Dictionary is desired instead of an IGrouping, the ToDictionary extension makes this simple:

Dictionary<string,List<string>> invertedDict = 
    inverted.ToDictionary(i => i.Key, i => i.ToList());

Linq invert a parent child sequence

2 Answers2