LINQ Grouping by Sum Value

Question

Say I have a class like so:

public class Work
{
    public string Name;
    public double Time;

    public Work(string name, double time)
    {
        Name = name;
        Time = time;
    }
 }

And I have a List<Work> with about 20 values that are all filled in:

List<Work> workToDo = new List<Work>();
// Populate workToDo

Is there any possible way that I can group workToDo into segments where each segments sum of Time is a particular value? Say workToDo has values like so:

Name | Time
A    | 3.50
B    | 2.75
C    | 4.25
D    | 2.50
E    | 5.25
F    | 3.75

If I want the sum of times to be 7, each segment or List<Work> should have a bunch of values where the sum of all the Times is 7 or close to it. Is this even remotely possible or is it just a stupid question/idea? I am using this code to separate workToDo into segments of 4:

var query = workToDo.Select(x => x.Time)
        .Select((x, i) => new { Index = i, Value = x})
        .GroupBy(y => y.Index / 4)
        .ToList();

But I am not sure how to do it based on the Times.

Answer 1

This solution recurses through all combinations and returns the ones whose sums are close enough to the target sum.

Here is the pretty front-end method that lets you specify the list of work, the target sum, and how close the sums must be:

public List<List<Work>> GetCombinations(List<Work> workList,
                                        double targetSum,
                                        double threshhold)
{
    return GetCombinations(0,
                           new List<Work>(),
                           workList,
                           targetSum - threshhold,
                           targetSum + threshhold);
}

Here is the recursive method that does all of the work:

private List<List<Work>> GetCombinations(double currentSum,
                                         List<Work> currentWorks,
                                         List<Work> remainingWorks,
                                         double minSum,
                                         double maxSum)
{
    // Filter out the works that would go over the maxSum.
    var newRemainingWorks = remainingWorks.Where(x => currentSum + x.Time <= maxSum)
                                          .ToList();
    // Create the possible combinations by adding each newRemainingWork to the 
    // list of current works.
    var sums = newRemainingWorks
                   .Select(x => new
                          {
                              Works = currentWorks.Concat(new [] { x }).ToList(),
                              Sum = currentSum + x.Time
                          })                                
                   .ToList();
    // The initial combinations are the possible combinations that are
    // within the sum range.                   
    var combinations = sums.Where(x => x.Sum >= minSum).Select(x => x.Works);
    // The additional combinations get determined in the recursive call.
    var newCombinations = from index in Enumerable.Range(0, sums.Count)
                          from combo in GetCombinations
                                        (
                                            sums[index].Sum,
                                            sums[index].Works,
                                            newRemainingWorks.Skip(index + 1).ToList(),
                                            minSum,
                                            maxSum
                                        )
                          select combo;
    return combinations.Concat(newCombinations).ToList();        
}

This line will get combinations that sum to 7 +/- 1:

GetCombinations(workToDo, 7, 1);

Answer 2

Here's a query that segments your data in groups where the times are near to 7, but not over:

Func<List<Work>,int,int,double> sumOfRange = (list, start, end) => list
                  .Skip(start)
                  .TakeWhile ((x, index) => index <= end)
                  .ToList()
                  .Sum (l => l.Time);

double segmentSize = 7;
var result = Enumerable.Range(0, workToDo.Count ())
    .Select (index => workToDo
                         .Skip(index)
                         .TakeWhile ((x,i) => sumOfRange(workToDo, index, i) 
                                              <= segmentSize));

The output for your example data set is:

A 3.5
B 2.75
total: 6.25

B 2.75
C 4.25
total: 7

C 4.25
D 2.5
total: 6.75

D 2.5
total: 2.5

E 5.25
total: 5.25

F 3.75
total: 3.75

If you want to allow a segments to total over seven, then you could increase the segmentSize variable by 25% or so (i.e. make it 8.75).

Answer 3

What you are describing is a packing problem (where the tasks are being packed into 7-hour containers). Whilst it would be possible to use LINQ syntax in a solution to this problem, there is no solution inherent in LINQ that I am aware of.