Reversing Dictionary using LINQ in C#

Question

How to convert

Dictioanry<String,List<String>> into Dictionary<String,String>

i'm having a dictionary like

Dictioanry<String,List<String>>dictOne=new Dictionary<String,List<String>>();

and which containg

Key(String)          Value(List<String>)

     A                a1,a2
     B                b1,b2
     C                c1

i need to convert the "dictOne" into

 Dictionary<String,String> dictReverse=new Dictionary<String,String>()

So the result will be like

Key(String)         Value(String)

   a1                  A
   a2                  A
   b1                   B
   b2                  B
   c1                   C

is there any way to do this using LINQ

Thanks in advance

Answer 1

// Associates each key with each of its values. Produces a sequence like:
// {A, a1}, {A, a2}, {B, b1}, {B, b2}, {C, c1}            
var kvps = from kvp in dictOne
           from value in kvp.Value
           select new { Key = kvp.Key, Value = value };    

// Turns the sequence into a dictionary, with the old 'Value' as the new 'Key'
var dictReverse = kvps.ToDictionary(kvp => kvp.Value, kvp => kvp.Key);

Of course, each key in the original dictionary must be associated with a unique set of values, and no key must be associated with values that are also associated with other keys.

Also bear in mind that Dictionary<K, V> does not define any sort of enumeration order. You can use the Enumerable.OrderBy method to enumerate the resulting dictionary in the appropriate order.

Answer 2

Update: As others have noted, in order for a dictionary to be truly "reversible" in this way, the values in your List<string> objects need to all be unique; otherwise, you cannot create a Dictionary<string, string> with an entry for every value in your source dictionary, as there would be duplicate keys.

Example:

var dictOne = new Dictionary<string, List<string>>
{
    { "A", new List<string> { "a1", "a2" } },
    { "B", new List<string> { "b1", "b2" } },
    { "C", new List<string> { "c1", "a2" } } // duplicate!
};

You have (at least) two options for dealing with this.

Option 1: Throw on duplicates

You may want to ensure that every element in every List<string> is, in fact, unique. In this case, a simple SelectMany with a ToDictionary will accomplish what you need; the ToDictionary call will throw an ArgumentException on encountering a duplicate value:

var dictTwo = dictOne
    .SelectMany(kvp => kvp.Value.Select(s => new { Key = s, Value = kvp.Key }))
    .ToDictionary(x => x.Key, x => x.Value);

The most generic way (that comes to mind) to abstract this functionality into its own method would be to implement an extension method that does this for any IDictionary<T, TEnumerable> implementation where TEnumerable implements IEnumerable<TValue>:

// Code uglified to fit within horizonal scroll area
public static Dictionary<T2, T1> ReverseDictionary<T1, T2, TEnumerable>(
    this IDictionary<T1, TEnumerable> source) where TEnumerable : IEnumerable<T2>
{
    return source
        .SelectMany(e => e.Value.Select(s => new { Key = s, Value = e.Key }))
        .ToDictionary(x => x.Key, x => x.Value);
}

The ugly proliferation of generic type parameters in the above method is to allow for types other than strictly Dictionary<T, List<T>>: it could accept a Dictionary<int, string[]>, for example, or a SortedList<string, Queue<DateTime>> -- just a couple of arbitrary examples to demonstrate its flexibility.

(A test program illustrating this method is at the bottom of this answer.)

Option 2: Skip duplicates

If duplicate elements in your List<string> values is a realistic scenario that you want to be able to handle without throwing an exception, I suggest you take a look at Gabe's excellent answer for an approach that uses GroupBy (actually, Gabe also provides a flexible approach that can cover either of these two cases based on a selector function; however, if you definitely want to throw on a duplicate, I'd still suggest the above approach, as it should be somewhat cheaper than using GroupBy).

Example program

Here's a little test program illustrating Option 1 above on a Dictionary<string, List<string>> with no duplicate elements in its List<string> values:

var dictOne = new Dictionary<string, List<string>>
{
    { "A", new List<string> { "a1", "a2" } },
    { "B", new List<string> { "b1", "b2" } },
    { "C", new List<string> { "c1" } }
};

// Using ReverseDictionary implementation described above:
var dictTwo = dictOne.ReverseDictionary<string, string, List<string>>();

foreach (var entry in dictTwo)
{
    Console.WriteLine("{0}: {1}", entry.Key, entry.Value);
}

Output:

a1: A
a2: A
b1: B
b2: B
c1: C

Answer 3

In the event that you would end up with duplicate keys in your result dictionary, you would have to pick a single one of those keys. Here's an implementation that just picks the first one it sees (using First):

var dictReverse = (from kvp in dictOne
                   from value in kvp.Value
                   group kvp.Key by value)
                   .ToDictionary(grp => grp.Key, grp => grp.First());

Given this input dictionary:

var dictOne = new Dictionary<string, IEnumerable<string>> { 
    { "C", new List<string> { "c1", "a2" } },
    { "B", new List<string> { "b1", "b2" } },
    { "A", new List<string> { "a1", "a2" } } };

The result would be:

c1: C
a2: C
b1: B
b2: B
a1: A

As Dan points out, you may want different behavior in the case of duplicate keys. You can create this function:

public static Dictionary<V, K> Transpose<K, V>(
    this Dictionary<K, IEnumerable<V>> dictOne,
    Func<IEnumerable<K>, K> selector)
{
    return (from kvp in dictOne
            from V value in kvp.Value
            group kvp.Key by value)
                .ToDictionary(grp => grp.Key, grp => selector(grp));
}

Then you could call it like dictOne.Transpose(Enumerable.First) to get the above behavior, dictOne.Transpose(Enumerable.Single) to get an exception when there's a duplicate key (the behavior of other posts), dictOne.Transpose(Enumerable.Min) to pick the first one lexicographically, or pass in your own function do whatever you need.