How to convert a dictionary of lists into a list of unique dictionaries according to a particular combinatorial logic?

Question

I have a dictionary of lists like so:

var dictOfLists = new Dictionary<string, List<string>>
{
    ["foo"] = new List<string>{ "a", "b", "c" },
    ["bar"] = new List<string>{ "d" },
    ["baz"] = new List<string>{ "e", "a" }
}

I want to convert this to a list of unique dictionaries like so:

var listOfUniqDicts = new List<Dictionary<string, string>>
{
    new Dictionary<string, string> {["foo"] = "a", ["bar"] = "d", ["baz"] = "e" },
    new Dictionary<string, string> {["foo"] = "a", ["bar"] = "d", ["baz"] = "a" },
    new Dictionary<string, string> {["foo"] = "b", ["bar"] = "d", ["baz"] = "e" },
    new Dictionary<string, string> {["foo"] = "b", ["bar"] = "d", ["baz"] = "a" },
    new Dictionary<string, string> {["foo"] = "c", ["bar"] = "d", ["baz"] = "e" },
    new Dictionary<string, string> {["foo"] = "c", ["bar"] = "d", ["baz"] = "a" },
}

(As you can see, in the above list, each of the dictionaries represents a unique combination of values, whose keys map to the respective keys of the initial dictionary.)

Is there a clean algorithm to do this with an arbitrary dictionary of the above type?

No, there is no predefined automatic API to do such a thing in one atomic call, as I know. Unless you are looking for a specialized mathematical set library and find it, you have to code the combination yourself. Certainly a moderately advanced LINQ query can do that... otherwise loops. — , Aug 07 '21 at 16:07
Does this answer your question? [Linq to return ALL pairs of elements from two lists?](https://stackoverflow.com/questions/3575925/) and [How to get all combinations of several List](https://stackoverflow.com/questions/17641769/) and [All Possible Combinations of a list of Values](https://stackoverflow.com/questions/7802822/) and [Generate all Combinations from Multiple (n) Lists](https://stackoverflow.com/questions/32571057/) and [Calculate all possible pairs of items from two lists?](https://stackoverflow.com/questions/1328079/) — , Aug 07 '21 at 16:23

score 1 · Accepted Answer · answered Aug 08 '21 at 08:33

It's like constructing a thruth table:

In the first column you write true, false, true, false, ...
In the second column you repeat each item 2 times: true, true false, false, true, true, false, false, ...
In the nth column you repeat each item 2^(n-1) times

This problem is a generalized version (try in dotnetfiddle):

private Dictionary<TKey, TValue>[] BuildDictionary<TKey, TValue>(Dictionary<TKey, List<TValue>> dict) where TKey : notnull
{
    // Calculating the size of the result (product of the length of each entry)
    int[] lengths = dict.Select(d => d.Value.Count()).ToArray();
    int size = lengths.Aggregate(1, (prev, val) => prev * val);   // reduce in JavaScript
    var result = new Dictionary<TKey, TValue>[size];

    for (int i = 0; i < result.Length; i++) { result[i] = new Dictionary<TKey, TValue>(); }

    int repeats = 1;
    foreach (var d in dict)
    {
        var key = d.Key;
        for (int row = 0; row < size;)
            for (int i = 0; i < repeats; i++)
                foreach (var val in d.Value)
                {
                    result[row].Add(key, val);
                    row++;
                }
        repeats *= d.Value.Count;
    }
    return result;
}

Result:

[
    {"foo":"a","bar":"d","baz":"e"},
    {"foo":"b","bar":"d","baz":"a"},
    {"foo":"c","bar":"d","baz":"e"},
    {"foo":"a","bar":"d","baz":"a"},
    {"foo":"b","bar":"d","baz":"e"},
    {"foo":"c","bar":"d","baz":"a"}
]

How to convert a dictionary of lists into a list of unique dictionaries according to a particular combinatorial logic?

1 Answers1