每个数字组合的递归函数

本文关键字：递归函数 组合 数字 | 更新日期: 2023-09-27 18:37:04

提供一些上下文：我正在开发一个算法问题构建器，最终用户可以在其中输入变量，为其分配范围和规则，在公式中使用它们并实现（x）数量的问题。

我目前需要使用变量名称 [a]、[b]、[c].. 等的键填充 x 数量的 x 个元素的字典，每个值都是唯一的，并且它们可能的范围的所有可能性; 即 a = 1 - 100，b = 1 - 50 等。

So 1st dict would be:
[a] = 1
[b] = 1
[c] = 1
2nd dict
[a] = 2
[b] = 1
[c] = 1

有没有一个简单的递归函数可以比迭代函数更好地处理这个问题？

感谢您的帮助！

每个数字组合的递归函数

如果我从一个可以表示您的值范围的结构开始，如下所示：

public struct Range
{
    public int Minimum { get; set; }
    public int Maximum { get; set; }
}

。那么我可以像这样表示您的输入：

var inputs = new Dictionary<string, Range>()
{
    { "a", new Range() { Minimum = 1, Maximum = 3 } },
    { "b", new Range() { Minimum = 1, Maximum = 2 } },
    { "c", new Range() { Minimum = 1, Maximum = 2 } },
};

。然后我可以像这样构建结果：

Func<IEnumerable<KeyValuePair<string, Range>>, IEnumerable<Dictionary<string, int>>> build = null;
build =
    kvps =>
    {
        if (kvps.Skip(1).Any())
        {
            return
                from kvp in kvps.Take(1)
                from n in Enumerable.Range(kvp.Value.Minimum, kvp.Value.Maximum - kvp.Value.Minimum + 1)
                from r in build(kvps.Skip(1))
                select new[] { new KeyValuePair<string, int>(kvp.Key, n) }.Concat(r).ToDictionary(x => x.Key, x => x.Value);
        }
        else
        {
            return
                from kvp in kvps
                from n in Enumerable.Range(kvp.Value.Minimum, kvp.Value.Maximum - kvp.Value.Minimum + 1)
                select new[] { new KeyValuePair<string, int>(kvp.Key, n) }.ToDictionary(x => x.Key, x => x.Value);
        }
    };

这将生成以下字典列表：

a=1， b=1， c=1a=1， b=1， c=2a=1， b=2， c=1a=1， b=2， c=2a=2， b=1， c=1a=2， b=1， c=2a=2， b=2， c=1a=2， b=2， c=2a=3， b=1， c=1a=3， b=1， c=2a=3， b=2， c=1a=3， b=2， c=2

以下是主查询的说明：

from kvp in kvps.Take(1)

从可枚举kvps中获取第一个元素（这是可枚举的"头"）

from n in Enumerable.Range(kvp.Value.Minimum, kvp.Value.Maximum - kvp.Value.Minimum + 1)

生成从Minimum到Maximum的所有n值。

from r in build(kvps.Skip(1))

递归调用列表"尾部"上的build以生成所有可能的尾部字典

select new[] { new KeyValuePair<string, int>(kvp.Key, n) }.Concat(r).ToDictionary(x => x.Key, x => x.Value);

创建一个带有Key和值的新KeyValuePair<string, int>[] n，并在创建新字典时连接尾部（r）中的每个值。

相关文章：