LINQ Grouping by amount of value

Question

Say I have a class like this:

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 populated:

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

Is there any possible way that I can group workToDo into segments where each sum of Time segments is a specific value? Let's say workToDo has these meanings:

 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 the times to be 7, each segment or List<Work> should have a bunch of values, where the sum of all Times is 7 or close to it. Is it even remotely possible or is it just a dumb question / idea? I use this code to split workToDo into 4 segments:

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

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

Answer 1

This decision is repeated through all combinations and returns those whose amounts are close enough to the target amount.

Here is a beautiful interface method that allows you to specify a work list, a target amount, and how to close amounts:

 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 a recursive method that does all 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 receive combinations that add up to 7 +/- 1:

 GetCombinations(workToDo, 7, 1); 

Answer 2

Here is a query that segments your data in groups, where the time is close to 7, but no more:

 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 sample dataset 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 segments to count more than seven, you can increase the segmentSize variable by 25% or so (i.e. make it 8.75).

Answer 3

What you describe is the packaging problem (where tasks are packed in 7-hour containers). Although LINQ syntax could be used to solve this problem, there is no solution inherent in LINQ that I know of.