递归检索字典的所有可能组合

Question

我看到了很多类似的问题，但是没有在这里找到我真正需要的。任何帮助表示赞赏。

我有一组键 (K[1..M])，每个键 K[i] 可以映射到此特定键 K[i]:V[i] 的一组可用值中的任何值,1..镍]

K[1]: V[1,1] | V[1,2] ... | V[1,N1]
K[2]: V[2,1] | V[2,2] ... | V[1,N2]
...
K[M]: V[M,1] | V[M,2] ... | V[1,NM]

我需要实现递归函数return枚举所有可能的 K-V 映射组合

例如：对于给定的集合：

K1: 1 | 2 | 3
K2: 4 | 1

组合如下：

(K1:1, K2:4)
(K1:2, K2:4)
(K1:3, K2:4)
(K1:1, K2:1)
(K1:2, K2:1)
(K1:3, K2:1)

理想情况下函数应该是这样的：

IEnumerable<Dictionary<TKey, TValue>> EnumerateAllPossibleCombinations(IEnumerable<TKey> keys, Func<TKey, IEnumerable<TValue>> getAvailableValuesForKey)
{
    ...
    yield return ...;
}

函数的使用（代码草稿）：

var allCombinations = EnumerateAllPossibleCombinations<string, int>(new[]{"K1","K2"}, k=>{
   switch k
   {
      case "K1": return new[]{1,2,3};
      case "K2": return new[]{4,1};
   }
   ThrowException("Unknown key");
});

上面例子的结果应该是 6 个字典，每个字典有 2 个键值对

我试图避免使用笛卡尔积，因为我需要接一个接一个地接收字典 (allCombinations.ElementAt(1), allCombinations.ElementAt(2))，而必须完全执行笛卡尔积对于所有组合，它可以 return 第一个字典。

Answer 1

您的解决方案基本上将采用（伪代码）的形式：

foreach (var key in dictionary)
    foreach (var value in dictionary)
        yield return new KeyValuePair(key, value)

如果需要传入谓词来约束值，可以这样插入：

foreach (var key in dictionary)
    foreach (var value in getAvailableValuesForKey)
        yield return new KeyValuePair(key, value)

实际代码看起来更接近于此（未经测试）：

foreach (var x in dictionary)
    foreach (var y in dictionary)
        yield return new KeyValuePair (x.key, y.value);

Answer 2

我相信这就是您要找的。

public static IEnumerable<IDictionary<TKey, TSource>> EnumerateAllPossibleCombinations<TKey, TSource>(
    IEnumerable<TKey> keys,
    Func<TKey, IEnumerable<TSource>> getAvailableValuesForKey)
{
    if (keys == null)
    {
        throw new ArgumentNullException("keys");
    }

    if (getAvailableValuesForKey == null)
    {
        throw new ArgumentNullException("getAvailableValuesForKey");
    }

    return keys.Any() ? 
           EnumerateAllPossibleCombinationsImp(keys.Distinct(), getAvailableValuesForKey) :
           Enumerable.Empty<IDictionary<TKey, TSource>>();
}

private static IEnumerable<IDictionary<TKey, TSource>> EnumerateAllPossibleCombinationsImp<TKey, TSource>(
    IEnumerable<TKey> keys,
    Func<TKey, IEnumerable<TSource>> getAvailableValuesForKey)
{
    if (!keys.Any())
    {
        yield return new Dictionary<TKey, TSource>();
        yield break;
    }

    var firstKey = keys.First();
    var values = getAvailableValuesForKey(firstKey) ?? Enumerable.Empty<TSource>();
    bool hasValues = values.Any();

    foreach (var value in values.DefaultIfEmpty())
    {
        foreach (var dictionary in EnumerateAllPossibleCombinationsImp(keys.Skip(1), getAvailableValuesForKey))
        {
            if (hasValues)
            {
                dictionary.Add(firstKey, value);
            }

            yield return dictionary;
        }
    }
}

首先，使用两个方法的原因是 keys 和 getAvailableValuesForKey 的 ArgumentNullException 将在调用方法时抛出，而不是在调用结果 IEnumerable 时抛出被迭代。接下来我们快速检查一下 keys 是否为空，如果是，我们只是 return 一个空的 IEnumerable。如果它不为空，那么我们调用包含主要实现的第二个方法。

第二种方法是递归的，所以首先我们设置我们的默认情况，即 keys 为空，在这种情况下我们产生一个空字典（这就是我们在第一种方法中进行空检查的原因）。然后我们通过从 keys 中获取第一项并检索该键的 values 来分解问题。如果 getAvailableValuesForKey returns null 对于那个键，我们将把它当作 returned 一个空集来代替（如果需要，这可以被视为异常情况） .然后我们检查是否有任何 values 并迭代它们，但如果有 none 我们使用 DefaultIfEmpty 插入一个默认值。这样做是为了让我们对一组空值进行一次迭代。然后我们进行递归调用，通过使用 Skip(1) 传递其余的键，对于每个 returned 字典，我们检查我们是否有任何键值，如果有，我们添加该键和值对到字典，无论哪种方式我们都会产生字典。这个想法是，最终递归调用将遇到没有键的情况，只有 return 一个空字典，然后在递归调用展开时将条目添加到其中。

递归检索字典的所有可能组合

Retrieve all possible combinations of dictionary recursively

c#

algorithm

combinations

combinatorics