Finding nearest sumElement combination in list

Question

I'm having some problem with finding nearest sumElement combination in list.

Example:

This is my list:

 list = {32183,15883,26917,25459,22757,25236,1657}
 list.Sum = 150092

And now I'm dividing

 list.Sum / z
 z = variable(user Input - in this example it's 3)

and I get

50031

Now I want to find closest number from listElement summs.

Closest to 50031 is

 32183 + 15883 = 48066
       or
 32183 + 15883 + 26917 = 74983

So I'm choosing 48066, next I want to find next element but we had to skip already counted elements(in this case I had to skip 32183 + 15883)

So now we can use only these elements 26917,25459,22757,25236,1657(not counted yet)

  26917 + 25459 = 52376
        or
  26917 + 25459 + 22757 = 75133

So I'm choosing 52376

and we doing this z(variable) times

We can sum elements in this order for exmaple we can't add

 32183 + 15883 + 1657

Because this skip couple list elements

We can sum elements in this sort, we CAN'T sort list. We can't do it because these numbers are lines amount from .csv file so I had to do it in this order.

For now I had:

for (int i = 0; i < z; i++)
{
    mid = suma/z ;

    najbliższy = listSum.Aggregate((x, y) => Math.Abs(x - mid) < Math.Abs(y - mid) ? x : y);
}

It finds me the 1st element (correctly) but I don't know how to loop it correctly. So I got only first element and in this example I need 3.

Can anyone help me to accomplish this?

Answer 1

The output from the following code is:

Target = 50031

32183 15883 Total: 48066
26917 25459 Total: 52376
22757 25236 1657 Total: 49650

You just need to call FindSubsetsForTotal() to receive a sequence of all the subsets, that you can just iterate over.

The code:

using System;
using System.Collections.Generic;

namespace Demo
{
    public class Program
    {
        static void Main()
        {
            var numbers = new[] {32183, 15883, 26917, 25459, 22757, 25236, 1657};
            int target = 50031;

            foreach (var subset in FindSubsetsForTotal(numbers, target))
            {
                int subtotal = 0;

                for (int i = subset.Item1; i <= subset.Item2; ++i)
                {
                    Console.Write(numbers[i] + " ");
                    subtotal += numbers[i];
                }

                Console.WriteLine("Total: " + subtotal);
            }
        }

        public static IEnumerable<Tuple<int, int>> FindSubsetsForTotal(IList<int> numbers, int target)
        {
            int i = 0;

            while (i < numbers.Count)
            {
                int end = endIndexOfNearestSum(numbers, i, target);
                yield return new Tuple<int, int>(i, end); // The subset is from i..end inclusive. Return it.
                i = end + 1;                              // On to the next subset.
            }
        }

        static int endIndexOfNearestSum(IList<int> numbers, int start, int target)
        {
            int sumSoFar    = 0;
            int previousSum = 0;

            for (int i = start; i < numbers.Count; ++i)
            {
                sumSoFar += numbers[i];

                if (sumSoFar > target)
                {
                    if (Math.Abs(sumSoFar - target) < Math.Abs(previousSum - target))
                        return i;

                    return i - 1;
                }

                previousSum = sumSoFar;
            }

            return numbers.Count - 1;
        }
    }
}

Answer 2

I have wrote code that seems to do what you describe. The idea is to keep a bin where the code will be adding contiguous numbers.

Contiguous because you say that we can't add if we

skip couple list elements

Now, when deciding to add to the bin, it will always try to do so if the total of the bin is less than the target value. And will only add if adding the new value makes the total closer to the target value. If those criteria are not met, then the number will not be added to the bin.

So, instead if the code decides to not add a number to the bin, then it will create a new bin. Now, at all times the best bin so far is stored, once the code is done with a bin, it compares it to that one and if it is better then replace it, if it is not just discard the current bin and start over.

These are my parameters:

var list = new List<int>{32183,15883,26917,25459,22757,25236,1657};
var sum = list.Sum();
var z = 3; // user input
var mid = (int)Math.Ceiling(sum / (double)z); // cutout point

Note: I'm using Ceiling for rounding because the sum (150092) divided by 3 is 50030.666666...

var bin = new List<int>();
var binTotal = 0;
var bestBin = bin;
var bestBinTotal = binTotal;
var candidatesCount = 0;

for(var index = 0; index < list.Count; index++)
{
    var current = list[index];
    var keep =
        (
            // The total of the bin is yet to reach the cutout point
            binTotal < mid
            // And adding the current will make it clouser
            && Math.Abs(mid - (binTotal + current)) < Math.Abs(mid - binTotal)
        )
        // but if this is the last candidate, screw that and add anyway
        || candidatesCount == (z - 1);
    if (keep)
    {
        bin.Add(current);
        binTotal += current;
    }
    else
    {
        candidatesCount++;
        if (Math.Abs(mid - binTotal) < Math.Abs(mid - bestBinTotal))
        {
            bestBin = bin;
            bestBinTotal = binTotal;
        }
        bin = new List<int>{current}; // because we didn't add it
        binTotal = current;
    }
}

Console.WriteLine("Result: {"+ string.Join(", ", bestBin) +"}; Total: " + bestBinTotal);

The output is Result: {32183, 15883}; Total: 48066

We can see that the distance from 48066 to 50031 is 1965, while the distance from 50031 to 52376 is 2345. So the code correctly decides that 48066 is closer.

Note: tested on LinqPad.

---

In fact the bins are only for storing the selected values, so if you don't need that you can remove them. If instead what you want is all the candidates you can modify the code as follows:

var candidates = new List<int>();
var binTotal = 0;
var bestBinTotal = binTotal;

for(var index = 0; index < list.Count; index++)
{
    var current = list[index];
    var keep =
        (
            // The total of the bin is yet to reach the cutout point
            binTotal < mid
            // And adding the current will make it clouser
            && Math.Abs(mid - (binTotal + current)) < Math.Abs(mid - binTotal)
        )
        // but if this is the last candidate, screw that and add anyway
        || candidates.Count == (z - 1);
    if (keep)
    {
        binTotal += current;
    }
    else
    {
        candidates.Add(binTotal);
        if (Math.Abs(mid - binTotal) < Math.Abs(mid - bestBinTotal))
        {
            bestBinTotal = binTotal;
        }
        binTotal = current; // because we didn't add it
    }
}

// Fix to add the final candidate:

candidates.Add(binTotal);

Console.WriteLine("Result: {"+ string.Join(", ", candidates) +"}; Best: " + bestBinTotal);

The output is Result: {48066, 52376, 49650}; Best: 48066