c# - 如何找出总和为100的数字的所有排列
问题描述
我试图找出一种有效的方法来创建一个方法,该方法采用一个包含多个连续整数列表的字典(每个列表必须从 0 或更高开始并在 100 或更低结束,但确切的数字可能会有所不同)并返回一个列表包含所有数字之和为 100 的所有排列的字典。
例如,对于 4 个类别:10 + 20 + 10 + 60 = 100
结果列表中的每个字典都应该为每个键存储一个整数值。
这是我想出的一些代码来说明我的问题:
using System;
using System.Collections.Generic;
using System.Linq;
namespace recursiveTest
{
class Program
{
static void Main(string[] args)
{
Dictionary<string, List<int>> data = new Dictionary<string, List<int>>();
data.Add("A", Enumerable.Range(0, 100).ToList());
data.Add("B", Enumerable.Range(0, 100).ToList());
data.Add("C", Enumerable.Range(0, 100).ToList());
data.Add("D", Enumerable.Range(0, 100).ToList());
// I would like to add a few entries more...
List<Dictionary<string, int>> permutations = new List<Dictionary<string, int>>();
foreach (var a in data["A"])
{
foreach (var b in data["B"])
{
foreach (var c in data["C"])
{
foreach (var d in data["D"])
{
if (a + b + c + d == 100)
{
var current = new Dictionary<string, int>()
{
["A"] = a,
["B"] = b,
["C"] = c,
["D"] = d,
};
permutations.Add(current);
}
}
}
}
}
Console.WriteLine($"Found (foreach): {permutations.Count()}");
Console.ReadKey();
}
}
}
使用 LINQ 的替代方法:
List<Dictionary<string, int>> permutations2 = (from a in data["A"]
from b in data["B"]
from c in data["C"]
from d in data["D"]
where a + b + c + d == 100
let current = new Dictionary<string, int>()
{
["A"] = a,
["B"] = b,
["C"] = c,
["D"] = d,
}
select current).ToList();
Console.WriteLine($"Found (LINQ): {permutations2.Count()}");
Console.ReadKey();
在类别(字典键)和数字开始增长之前,这并不是一项非常复杂的任务......由于字典键(类别)的数量可能会有所不同,这似乎是递归的潜在候选者,但我不是不能让它工作。这两个版本有一些明显的缺点:
- 一旦项目和/或类别的数量增加,性能就会突然下降。
- 箭头形代码似乎是灾难的根源。
- 它试图遍历所有可能的组合,而实际上只有少数是有用的(总和为 100 的组合)。
用简短易读的代码和良好的性能实现预期结果的最佳方法是什么?
有没有办法在尝试找出这 100 个总和值时过滤掉不必要的循环?
编辑: 为了澄清起见,我的想法是能够定义一个带有这样签名的方法:
private static List<Dictionary<string, int>> GetValidPermutations(Dictionary<string, List<int>> data)
然后像这样调用它:
List<Dictionary<string, int>> permutations = GetValidPermutations(data);
解决方案
要提高性能,关键是减少不必要的迭代次数:
static List<Dictionary<string, int>> GetValidPermutations(int target, Dictionary<string, List<int>> data)
{
return GetValidPermutations(target, data, 0, new int[data.Count])
.Select(perm => CreateDictionary(data.Keys, perm))
.ToList();
}
static Dictionary<string, int> CreateDictionary(IEnumerable<string> keys, IEnumerable<int> values)
{
return keys.Zip(values, KeyValuePair.Create)
.ToDictionary(pair => pair.Key, pair => pair.Value);
}
static IEnumerable<int[]> GetValidPermutations(int target, Dictionary<string, List<int>> data, int level, int[] sequence)
{
if (level < sequence.Length)
{
var currentList = data.ElementAt(level).Value;
var subsequentLists = data.Skip(level + 1).Select(x => x.Value);
int start = Math.Max(currentList[0], target - subsequentLists.Sum(x => x.Last()));
int end = Math.Min(currentList.Last(), target - subsequentLists.Sum(x => x[0]));
for (sequence[level] = start; sequence[level] <= end; sequence[level]++)
{
int subTarget = target - sequence[level];
foreach (var perm in GetValidPermutations(subTarget, data, level + 1, sequence))
{
yield return perm;
}
}
}
else
{
var perm = sequence.Append(target);
System.Diagnostics.Debug.Assert(perm.Sum() == 100);
yield return perm.ToArray();
}
}
以上start
及end
以上经过仔细计算,仅包括必要的迭代。其他值被跳过,因为它们不能形成排列。
然后你可以像这样调用方法:
var p4 = GetValidPermutations(100, data);
Console.WriteLine($"Found (Recursion): {p4.Count()}");
一开始可能很难理解递归版本,有for循环等价物,可以看到一些代码部分重复了:
const int TARGET = 100;
var permutations3 = new List<Dictionary<string, int>>();
int aStart = Math.Max(data["A"][0], TARGET - data["B"].Last() - data["C"].Last() - data["D"].Last());
int aEnd = Math.Min(data["A"].Last(), TARGET - data["B"][0] - data["C"][0] - data["D"][0]);
for (int a = aStart; a <= aEnd; a++)
{
int bStart = Math.Max(data["B"][0], TARGET - a - data["C"].Last() - data["D"].Last());
int bEnd = Math.Min(data["B"].Last(), TARGET - a - data["C"][0] - data["D"][0]);
for (int b = bStart; b <= bEnd; b++)
{
int cStart = Math.Max(data["C"][0], TARGET - a - b - data["D"].Last());
int cEnd = Math.Min(data["C"].Last(), TARGET - a - b - data["D"][0]);
for (int c = cStart; c <= cEnd; c++)
{
var perm = new Dictionary<string, int>
{
{ "A", a },
{ "B", b },
{ "C", c },
{ "D", TARGET - a - b - c }
};
System.Diagnostics.Debug.Assert(perm["D"] >= data["D"][0] && perm["D"] <= data["D"].Last());
permutations3.Add(perm);
}
}
}
Console.WriteLine($"Found (for): {permutations3.Count()}");
跳过逻辑可以通过以下示例来说明:
假设 B、C、D 的最大值分别为 10、20、30,则 A 需要至少为 40 才能有 100。这样 A 可以从 40 开始,跳过 0-39(如果有) .
类似的逻辑可以应用于跳过更高的范围。假设 B、C、D 的最小值分别为 5、10、15,那么 A 不能超过 70。因为这样总和会超过 100。所以我们可以在 A 超过 70 时停止循环。
对所有类别应用跳过逻辑可以导致上述代码。另外,最后一个类别可以直接计算,无需循环。
推荐阅读
- javascript - 不明白为什么类似的测试通过了 1 而不是另一个,无法发现
- scala - 使用带有 scalajs 的套接字
- python - 在 Python 中处理未实现的参数
- javascript - webpack 包显示未定义后在浏览器中调用的对象
- c# - 如何仅在首次安装时运行活动?
- azerothcore - 卡在“检索字符列表”
- ruby - 在 Pry REPL 中加载 *.rb 文件
- c# - 父类静态变量保持不变
- powershell - 我在 regedit 中将背景上下文菜单编辑为“在此处打开 power shell”,如何以管理员身份打开它?
- android - 支持 LG Q7+ 的 ARCore