Geek Answers Handbook

How to find the relevant records in the data table

I have a data table with two columns: number and date, for example:

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

Now I want to search for all records sorted by date, where the sum of the number corresponds to 500. I can easily see that the first, third and fourth records (125 + 150 + 225 = 500) provide a match , but for programming this, I can only think about to go through the data table a million times until I find the right match.

Is there a smarter idea?

+4
source share
1 answer

In the worst case scenario, you need to go through all subsets of 2^nyour dataset, but if all your objects are non-negative, you can start by filtering by item.Number <= 500.

Here is a possible method Subsets(actually the answer to How to get all subsets of an array?, But don't tell them):

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 })));
}

Once you have a method Subsets, you can filter the result as follows, although the performance is still about gazillion (or 2^nif you want to be picky).

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

However, if you have a restriction on the Numberfact that it is non-negative, you can combine the operation Subsetswith the search for the target amount. That would mean that you define

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 , , .

+2

More articles:


All Articles