如何在数据表中查找匹配记录

Question

如何在数据表中查找匹配记录

c#datatablesum

4

我有一个数据表，其中包含两列：数字和日期，例如：

125 | 2013/10/20 100 | 2013/10/21 150 | 2013/10/24 225 | 2013/10/24 250 | 2013/10/28 310 | 2013/10/30

现在，我想按日期搜索所有记录，并使数字之和匹配为500。我可以轻松地看到第一、第三和第四条记录（125 + 150 + 225 = 500）提供了匹配，但是要编写这样的程序，我只能想到通过数据表数百万次，直到找到正确的匹配。

有没有更聪明的主意？

- Menno

可能是重复的问题：如何在LINQ（到数据集）中计算DataTable列的总和？ - Liam

你有多少条记录？ - Aage

@bump - 可能超过一千 - Menno

可能是查找所有可能的数字组合以达到给定总和的重复问题。 - mbeckish

2

这是子集和问题。 - mbeckish

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rob Lyndon · Accepted Answer

在最坏的情况下，您确实需要遍历数据集的所有2^n个子集，但如果您的所有项都是非负数，则可以从过滤掉“item.Number <= 500”开始。

这里是一个可能的“Subsets”方法（实际上是如何获取数组的所有子集？的答案，但不要告诉他们）：

public static IEnumerable<IEnumerable<T>> Subsets(this IEnumerable<T> source)
{
    var first = source.FirstOrDefault();
    if (first == null) return new[] { Enumerable.Empty<T>() };

    var others = source.Skip(1).Subsets();
    return others.Concat(others.Select(s => s.Concat(new { first })));
}

一旦你有了Subsets方法，你可以按以下方式过滤结果，尽管性能仍然是数量级为亿万（或者如果你想挑剔的话，是2^n）。

var sets = items.Where(i => i.Number <= 500)
    .Subsets().Where(s => s.Sum(i => i.Number) == 500);

然而，如果您对“Number”有非负的限制，您可以将“Subsets”操作与搜索目标和结合起来。这意味着您需要定义：

public static IEnumerable<IEnumerable<T>> SubsetsAddingUpTo(this IEnumerable<T> source, int target)
{
    // This stopping condition ensures that you will not have to walk the rest of the tree when you have already hit or exceeded your target.
    // It assumes that the Number values are all non-negative.
    if (target < 0) return Enumerable.Empty<IEnumerable<T>>();

    var first = source.FirstOrDefault();
    if (first == null) return Enumerable.Empty<IEnumerable<T>>();

    var tail = source.Skip(1).Where(i => i.Number <= target).ToList();

    var othersIncludingFirst = tail.SubsetsAddingUpTo(target - first.Number);
    var othersExcludingFirst = tail.SubsetsAddingUpTo(target);

    return othersExcludingFirst.Concat(othersIncludingFirst.Select(s => s.Concat(new { first })));
}

因为方法内部会检查 "<= target"，所以你不需要进行任何预过滤。但是，在搜索之前可以对数据进行排序，以按照日期层次顺序给出结果集。调用方式如下：

var sets = items.OrderByDescending(i => i.Date).SubsetsAddingUpTo(500);

这实际上应该给你相当不错的性能。最坏情况（每个项目的数字为0或1）不会很好（顺序2^n），但是如果大多数Number的值与您的目标总和具有类似的数量级，就像您的示例一样，那么停止条件将挺身而出，为您节省大量不必要的操作。