Allocate money in particular order

Question

I have an total amount payable by an Employer this amount needs to be split amongst staff.

For example

a $100
b $200
c -$200
d -$200
e $500

The total amount payable is the sum of all items, in this case $400

The problem is I must call a 3rd party system to assign these amounts one by one. But I cannot let the balance go below $0 or above the total amount ($400) during the allocation.

So if I insert in the above order a,b,c will work so the current allocated sum = 100 + 200 - 200 = $100. However when I try to allocate d. The system will try to add -$200 which will make the current allocated sum -$100 which is < $0 which is not allowed so it will be rejected by the system.

If I sort the list so negative items are last. i.e.

a $100
b $200
e $500
c -$200
d -$200

a will work, b will work, but when it tries to insert e there will be insufficient funds error because we have exceeded the maximum of $400. I have come to the realisation that there is no silver bullet and there will always be scenarios what will break. However I wanted to come up with a solution that would work most of the time.

Normal sample of data would have between 5 - 100 items. With only 2-15% of those containing negative amounts.

Is there a clever way I can sort the list? Or would it be better just to try an allocated multiple times. For example split the positive and negatives into two list. Insert positives until one errors, then insert negatives until it errors then switch back and forth between the list until it is all allocated or until both of them error.

Answer 1

Although this effectively the same as Haile's answer (I started working on an answer before he posted his, and beat me to the punch) I thought I would post it anyway since it includes some source code and may help someone who wants a concrete implementation (sorry that it's not in C#, C++ is the closest thing I have access to at the moment)

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

vector<int> orderTransactions(const vector<int>& input) {

    int max = accumulate(input.begin(), input.end(), 0);

    vector<int> results;
    // if the sum is negative or zero there are no transactions that can be added
    if (max <= 0) {
        return results;
    }

    // split the input into positives and negatives
    vector<int> sorted = vector<int>(input);
    sort(sorted.begin(), sorted.end());

    vector<int> positives;
    vector<int> negatives;

    for (int i = 0; i < sorted.size(); i++) {
        if (sorted[i] >= 0) {
            positives.push_back(sorted[i]);
        } else {
            negatives.push_back(sorted[i]);
        }
    }   

    // try to process all the transactions
    int sum = 0;
    while (!positives.empty() || !negatives.empty()) {
        // find the largest positive transaction that can be added without exceeding the max
        bool positiveFound = false;

        for (int i = (int)positives.size()-1; i >= 0; i--) {
            int n = positives[i];
            if ((sum + n) <= max) {
                sum += n;
                results.push_back(n);
                positives.erase(positives.begin()+i);
                positiveFound = true;
                break;
            }
        }

        if (positiveFound == true) {
            continue;
        }

        // if there is no positive find the smallest negative transaction that keep the sum above 0
        bool negativeFound = false;
        for (int i = (int)negatives.size()-1; i >= 0; i--) {
            int n = negatives[i];
            if ((sum + n) >= 0) {
                sum += n;
                results.push_back(n);
                negatives.erase(negatives.begin()+i);
                negativeFound = true;
                break;
            }
        }

        // if there is neither then this as far as we can go without splitting the transactions
        if (!negativeFound) {
            return results;
        }
    }

    return results;
}


int main(int argc, const char * argv[]) {

    vector<int> quantities;
    quantities.push_back(-304);
    quantities.push_back(-154);
    quantities.push_back(-491);
    quantities.push_back(-132);
    quantities.push_back(276);
    quantities.push_back(-393);
    quantities.push_back(136);
    quantities.push_back(172);
    quantities.push_back(589);
    quantities.push_back(-131);
    quantities.push_back(-331);
    quantities.push_back(-142);
    quantities.push_back(321);
    quantities.push_back(705);
    quantities.push_back(210);
    quantities.push_back(731);
    quantities.push_back(92);
    quantities.push_back(-90);

    vector<int> results = orderTransactions(quantities);

    if (results.size() != quantities.size()) {
        cout << "ERROR: Couldn't find a complete ordering for the transactions. This is as far as we got:" << endl;
    }

    for (int i = 0; i < results.size(); i++) {
        cout << results[i] << endl;
    }

    return 0;
}

Answer 2

What I think you want to do here is:

1. Filter out any values that will always fail
2. Order the transactions by smallest absolute value - smaller transactions means we can do more before we hit the limit
3. Keep processing positives until the next one will cause us to go over the limit
4. Keep processing negatives until we either run out of negatives or the next one would take us under $0
5. Repeat 3-4

I've not tested the code below, but it should be vaguely the right shape:

var validValues = values
    .Where(v => Math.Abs(v) < upperLimit) //filter out anything that will always fail
    .OrderBy(v => Math.Abs(v)); //sort by the absolute value (to maximise # of transactions)

var additions              = validValues.Where(v => v >= 0);
var subtractionsEnumerator = validValues.Where(v => v < 0).GetEnumerator();
var currentTotal           = 0.0;

//go through all of the additions
foreach (var addition in additions)
{
    if (currentTotal + addition > upperLimit) //would the next addition take us over the limit?
    {
        //keep processing negative values until the next one would take us past $0
        while (subtractionsEnumerator.MoveNext() && currentTotal + subtractionsEnumerator.Current > 0)
        {
            currentTotal += subtractionsEnumerator.Current;
        }
    }

    if (currentTotal + addition > upperLimit) //if we weren't able to reduce by enough
        throw new Exception("Can't process transactions");

    currentTotal += addition;
}

//do we have any left over negatives?  better process those as well
while (subtractionsEnumerator.MoveNext())
{
    if (currentTotal + subtractionsEnumerator.Current < 0)
        throw new Exception("Can't process transactions");

    currentTotal += subtractionsEnumerator.Current;
}