C# split integer in parts given part weights algorithm

user_3096657 0
Viewed 554

I have an integer and a list of non-negative weights, how can I 'split' the integer into same number of 'buckets' with corresponding weights? 

public int[] SplitIntoBuckets(int count, int[] weights) {
    // some magic algorithm
    Debug.Assert(solution.Sum() == count);
    return solution;
}

A trivial example would be count = 200 and weights = { 25, 25, 50 } with solution {50, 50, 100} (50+50+100 = 200). The inputs, however, does not have to be 'nice' numbers, another example without nice solution would be count = 150 and weights {753, 42, 95, 501}.
The sum of buckets must be always equal to the count input, the algorithm should distribute the input among buckets as closely to weights as possible. What is as 'close as possible' does not matter (for example it could be either lowest absolute, relative or squared error).
The closest questions I could find are Split evenly into buckets, however my buckets are not 'even' and Split randomly into buckets however the weights are chosen randomly to be 'nice' numbers.

double integer algorithm c#
2 Answers

I suggest rounding while tracking difference (diff) between exact double value (v) and rounded integer one (value):

public static int[] SplitIntoBuckets(int count, int[] weights) {
  if (null == weights)
    throw new ArgumentNullException(nameof(weights));
  else if (weights.Length <= 0)
    return new ArgumentOutOfRangeException(nameof(weights), "Empty weights");  

  double sum = weights.Sum(d => (double)d);

  if (sum == 0)
    throw new ArgumentException("Weights must not sum to 0", nameof(weights));

  Func<double, int> round = (double x) => (int)(x >= 0 ? x + 0.5 : x - 0.5);

  int[] result = new int[weights.Length];
  double diff = 0;

  for (int i = 0; i < weights.Length; ++i) {
    double v = count * (double)(weights[i]) / sum;
    int value = round(v);
    diff += v - value;

    if (diff >= 0.5) {
      value += 1;
      diff -= 1;
    }
    else if (diff <= -0.5) {
      value -= 1;
      diff += 1;
    }

    result[i] = value;
  }
    
  return result;
}

Demo:

string demo = sstring.Join(Environment.NewLine, Enumerable
  .Range(200, 15)
  .Select(n => $"{n} = {string.Join(", ", SplitIntoBuckets(n, new int[] { 25, 25, 50 }))}"));

Console.Write(demo);

Outcome:

200 = 50, 50, 100
201 = 50, 51, 100
202 = 51, 50, 101
203 = 51, 51, 101
204 = 51, 51, 102
205 = 51, 52, 102
206 = 52, 51, 103
207 = 52, 52, 103
208 = 52, 52, 104
209 = 52, 53, 104
210 = 53, 52, 105
211 = 53, 53, 105
212 = 53, 53, 106
213 = 53, 54, 106
214 = 54, 53, 107
user_23194070

Notice that solution[i] is equal to:

round(weights[i] / weightSum * count)

There is an edge case where weights[i] / weightSum * count is an odd multiple of a half (x.5), which causes round to round up an extra time unnecessarily. An example of this would be count = 3, weights = { 1, 1 }. To counter this, we calculate the last bucket by subtracting the sum of the previous buckets from count. This would ensure the solution to add up to count no matter what.

public int[] SplitIntoBuckets(int count, int[] weights) {
    int[] solution = new int[weights.Length];
    int weightSum = weights.Sum();
    // for every weight except the last...
    int sum = 0;
    for (int i = 0 ; i < weights.Length - 1 ; i++) {
        solution[i] = (int)Math.Round((double)weights[i] / weightSum * count);
        sum += solution[i];
    }
    // calculate the last bucket by subtracting:
    solution[weights.Length - 1] = count - sum;
    return solution;
}
user_51335850
Related