How can I make a new set of dictionaries containing all the possible combinations from a dictionary with list as value

Question

I need to take a dictionary with a string key and a list of strings as value and find all combinations that it can make. For example:

var myDictionary = new Dictionary<string, List<string>>
{
    {"X", new List<string> {"x", "y", "z"}},
    {"Y", new List<string> {"x", "y"}},
    {"Z", new List<string> {"a", "b"}}
};

Will translate to:

{X: x, Y: x, Z: a}
{X: x, Y: x, Z: b}
{X: x, Y: y, Z: a}
{X: x, Y: y, Z: b}
{X: y, Y: x, Z: a}
{X: y, Y: x, Z: b}
{X: y, Y: y, Z: a}
{X: y, Y: y, Z: b}
{X: z, Y: x, Z: a}
{X: z, Y: x, Z: b}
{X: z, Y: y, Z: a}
{X: z, Y: y, Z: b}

How can I do this the smartest way?

What have to tried so far that wasn't successful? Or how do you think this could be accomplished? — Adam Porad, Oct 31 '14 at 21:13
This question might help: [Generating all Possible Combinations](http://stackoverflow.com/q/3093622/10263) — Brian Rogers, Oct 31 '14 at 21:40

Enigmativity · Answer 1 · 2014-11-18T07:57:18.610

How about doing it like this?

var combinations =
    from x in myDictionary["X"]
    from y in myDictionary["Y"]
    from z in myDictionary["Z"]
    select new Dictionary<string, string>()
    {
        { "X", x },
        { "Y", y },
        { "Z", z },
    };

I get this result:

combinations

After some further thought here is a method to compute with any number of elements in the dictionary (i.e. not just "X", "Y", & "Z".)

Func<
    Dictionary<string, string>,
    Dictionary<string, string>,
    Dictionary<string, string>> merge = (d1, d2) =>
{
    var d = new Dictionary<string, string>(d1);
    foreach (var kv in d2)
    {
        d.Add(kv.Key, kv.Value);
    }
    return d;
};

var combinations =
    myDictionary
        .Select(x =>
            x.Value.Select(v =>
                new Dictionary<string, string>()
                {
                    { x.Key, v }
                }))
        .Aggregate((xs, vs) =>
            from x in xs
            from v in vs
            select merge(x, v));

score 1 · Answer 2 · edited Oct 31 '14 at 22:10

1

This will work for your specific example. Hopefully this gives you a start, and it shouldn't be too hard to make it work for a more general approach:

var dict = new Dictionary<string, List<string>>
{
    {"X", new List<string> {"x", "y", "z"}},
    {"Y", new List<string> {"x", "y"}},
    {"Z", new List<string> {"a", "b"}}
};

var combiDicts = new List<Dictionary<string, string>>();
foreach (var entryXItem in dict["X"])
{
    foreach (var entryYItem in dict["Y"])
    {
        foreach (var entryZItem in dict["Z"])
        {
            combiDicts.Add(new Dictionary<string, string>
            {
                {"X", entryXItem}, {"Y", entryYItem}, {"Z", entryZItem}
            });
        }
    }
}

Test:

foreach (var d in combiDicts)
    Console.WriteLine("{{X: {0}, Y: {1}, Z: {2}}}", d["X"], d["Y"], d["Z"]);

Output:

{X: x, Y: x, Z: a}
{X: x, Y: x, Z: b}
{X: x, Y: y, Z: a}
{X: x, Y: y, Z: b}
{X: y, Y: x, Z: a}
{X: y, Y: x, Z: b}
{X: y, Y: y, Z: a}
{X: y, Y: y, Z: b}
{X: z, Y: x, Z: a}
{X: z, Y: x, Z: b}
{X: z, Y: y, Z: a}
{X: z, Y: y, Z: b}

edited Oct 31 '14 at 22:10

Tim Schmelter

450,073
74
686
939

answered Oct 31 '14 at 21:35

Rufus L

36,127
5
30
43

I think the output needs to be a `List>` (which would not be hard to convert your answer in to) – Scott Chamberlain Oct 31 '14 at 21:37
From the syntax of the examples in the original unupdated question it looks like he was expecting dictionaries in to dictionaries out. – Scott Chamberlain Oct 31 '14 at 21:39
1

@RufusL: look at the title: _"How can I make a new set of dictionaries"_. However, it should be simple, every dictionary contains one x-key/value, one y-key/value and one z-key/value. – Tim Schmelter Oct 31 '14 at 21:39
I guess I don't understand what he's looking for, then. In his output, there is no unique key for any of the lines...you need to combine x, y, and z to get a unique key for each line. And when you get that key, what would be the value? – Rufus L Oct 31 '14 at 21:43
@RufusL: you could add this: `combiDicts.Add(new Dictionary { {"X", entryXItem}, {"Y", entryYItem}, {"Z", entryZItem} });` +1 even if it could contain repetitions – Tim Schmelter Oct 31 '14 at 21:43
please feel free to edit my answer (or duplicate it as your own and i'll delete mine). I don't understand what a KeyValuePair item would look like in the resulting dictionary. – Rufus L Oct 31 '14 at 21:46

How can I make a new set of dictionaries containing all the possible combinations from a dictionary with list as value

2 Answers2