如何根据特定的组合逻辑将列表字典转换为唯一字典列表？

Question

我有一个这样的列表字典：

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" }
}

我想将其转换为独特词典的列表，如下所示：

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" },
}

（如您所见，在上面的列表中，每个字典代表一个唯一的值组合，其键映射到初始字典的相应键。）

是否有一个干净的算法可以使用上述类型的任意字典来执行此操作？

Answer 1

这就像构建一个真理table:

在第一列中写真、假、真、假...
在第二列中，您将每个项目重复 2 次：true、true false、false、true、true、false、false ...
在第 n 列中，您将每个项目重复 2^(n-1) 次

此问题为通用版（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;
}

结果：

[
    {"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?

c#

combinations

dictionary

list

combinatorics