Distribute values equally in count and sum to a set of users

Question

I have a table with 100 float values (say AMOUNT) that need to be equally divided among 5 users (say UID 1 to 5). The distribution must be such that each user gets approximately the same total count and value of AMOUNT.

Say, I have a sample table with 20 Amounts:

164548.65, 148410.72, 131395.33, 130219.97, 128593.28, 
124539.92, 103958.45, 103671.87, 100210.36,  99645.42,
 98848.25,  97764.84,  97577.03,  90067.98,  87838.22, 
 86730.85,  85508.00,  83481.78,  82886.95,  78588.79

This needs to be divided among 5 codes (numbered 1-5) in such a manner that each code gets 4 Amounts with a net worth of approx 424,000.

I am using SQL Server.

The Amounts are Linked to Invoice numbers. So the table has Invoice_Number,Amount. I need to add a column where the USER_ID (1-4) can be plugged in. So if there are 20 Invoices and 4 users, each user gets assigned with 5 Invoices and the sum of Invoice Amounts for each user must approximately be the same.

Answer 1

Do we have any idea of the distribution of the values ?

A super basic way of handling that, assuming the distribution of the different values of amount are more or less uniform could be split values into N / number_of_values parts (using ntile() function and ordering by amount)

So something like :

select  amount, 
        row_number() over(partition by id order by amount) as id
from (
    select amount, ntile(4) over(order by amount) as id
    from test
    )t
order by 2,1

With the sample data you gave, we get sum 394665.71, 403385.26, 416126.01, 435642.01, 474667.67

Not exactly what you expected but not so far.

A less super basic way could be trying to split in a different way : after the ntile statement, we have 4 buckets of 5 values, the highest values in bucket #1, the lowest in #2.

• Let add the highest value of bucket #1 with the lowest of #2, with the highest of #3, with the lowest of #4.
• And the second highest value of bucket #1 with the second lowest of #2, with the second highest of #3, with the second lowest of #4.
• Etc...

So :

select  amount, 
        case 
            when id % 2 != 0 then row_number() over(partition by id order by amount) 
            else row_number() over(partition by id order by amount desc) 
        end as uid
from (
    select amount, ntile(4) over(order by amount) as id
    from test
    ) t
order by 2,1

With sum 427702.27, 409754.4, 416126.01, 429272.87, 441631.11

For something more accurate, this is more for statistician experts I think.

Answer 2

I would try using a cursor for a problem like this. It's not clear how close you need the sums to be to each other, but to get closer to an optimal solution you may need complicated row by row logic and you may need to make small tweaks to your algorithm as you test against different data sets. It may be difficult to implement those algorithms using a traditional set-based solution.

Below is an implementation of an algorithm that processes all amounts in descending order and adds them to the id with the smallest total at that point.

Here is code for your test data:

-- DROP TABLE #X_TEST_DATA

CREATE TABLE #X_TEST_DATA (amount FLOAT);

-- test data
INSERT INTO #X_TEST_DATA
VALUES 
(164548.65), (148410.72), (131395.33), (130219.97), (128593.28),
(124539.92), (103958.45), (103671.87), (100210.36), (99645.42),
(98848.25), (97764.84), (97577.03), (90067.98), (87838.22),
(86730.85), (85508.00), (83481.78), (82886.95), (78588.79);

Here is the code do calculate the groups:

DECLARE
@num_of_users INTEGER = 5,
@max_assignments INTEGER = 4,
@id_to_update INTEGER,
@amount FLOAT;
BEGIN
    SET NOCOUNT ON;

    DECLARE @results_table TABLE (ID int, AMOUNT FLOAT); -- table variable to store results

    -- summary table to update after each row is processed. this avoids scans on @results_table
    DECLARE @summary_table TABLE (ID int, NUM_OF_ASSIGNMENTS INT, TOTAL_AMOUNT FLOAT); 

    INSERT INTO @summary_table
    SELECT N, 0, 0
    FROM dbo.GetNums(@num_of_users); -- this is a TVF that generates integers

    DECLARE amount_cursor CURSOR LOCAL FAST_FORWARD
    FOR 
    SELECT amount
    FROM #X_TEST_DATA
    ORDER BY amount DESC; 
    OPEN amount_cursor;

    FETCH NEXT FROM amount_cursor INTO @amount;

    WHILE @@FETCH_STATUS = 0  
    BEGIN
        SELECT @id_to_update = ID
        FROM 
        (
            SELECT ID, ROW_NUMBER() OVER (ORDER BY TOTAL_AMOUNT ASC, ID ASC) RN
            FROM @summary_table
            WHERE NUM_OF_ASSIGNMENTS < @max_assignments
        ) t
        WHERE t.RN = 1; -- add the new amount to the id with the smallest TOTAL_AMOUNT that still has room

        UPDATE @summary_table
        SET NUM_OF_ASSIGNMENTS = NUM_OF_ASSIGNMENTS + 1, TOTAL_AMOUNT = TOTAL_AMOUNT + @amount
        WHERE id = @id_to_update;

        INSERT INTO @results_table (ID, AMOUNT)
        SELECT @id_to_update, @amount;

        FETCH NEXT FROM amount_cursor INTO @amount;
    END;  
    CLOSE amount_cursor;  
    DEALLOCATE amount_cursor;  

    SELECT rt.ID, rt.AMOUNT, st.TOTAL_AMOUNT, st.NUM_OF_ASSIGNMENTS
    FROM @results_table rt
    LEFT OUTER JOIN @summary_table st ON rt.ID = st.ID;    
END;

For the example data set in the question I get sums of:

418534.67
419562.89
426682.96
429085.06
430621.08

With cursors you need to be especially aware of performance because SQL Server does the processing row by row which often is slower than a well-optimized set-based solution. However, the code above was able to process 100000 rows in 4 seconds on my machine.

Answer 3

One approach which is conceptually equivalent to that of @irimias, which consists on doing two things:

First: Sort your amounts (it doesn't really matter if asc or desc):

 78588.79
 82886.95
 83481.78
 85508.00
 86730.85
 87838.22
 90067.98
 97577.03
 97764.84
 98848.25
 99645.42
100210.36
103671.87
103958.45
124539.92
128593.28
130219.97
131395.33
148410.72
164548.65

Second: Assign to each of those (sorted values), a number from a periodic up-and-down sequence

1
2
3
4
5
5
4
3
2
1
1
2
3
4
5
5
4
3
2
1

Add all the amounts assigned to (1) -> this is the amount for code (1).

Code (1) gets the smallest of the first ten values, and also the biggest of the first ten values, also the smaller of the second group of 10 values, and the biggest one, and so on. Code (2) will take the second smallest and second biggest, and so on, and so forth.

This requires a bit more of SQL than I'd like, and I've needed a very friendly community help to make it 'SQL Server friendly' (see How to generate a 1, 2, 3, 3, 2, 1, 1, 2, 3, 3, 2, 1, … series).

With that in mind, here comes my proposal:

These are just parameters

DECLARE @n int ;
DECLARE @m int ;

SET @n = 5 ;  -- Number of 'codes'
SET @m = 4 ;  -- Number of 'repetitions' (20 / 5)

This is the way to generate an "up and down sequence":

-- We need a sequence of numbers, for convenience.
-- There must be more than @n and more than @m
WITH numbers(v) AS
(
    SELECT x
    FROM (VALUES(1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) 
    AS n(x)
)

-- This nice computation will give us a sequence of the
-- form (1, 2, ... @n, @n, ... 2, 1) x @m
, up_and_down_sequence(i, code) AS
(
SELECT  
    @n*(up_down+2*m) + n AS i, n*(1-up_down) + ABS(-@n-1+n)*up_down AS code
FROM 
               (SELECT TOP(@n)   v FROM numbers ORDER BY v ASC) n(n)
    CROSS JOIN (VALUES(0), (1))                                 s(up_down)
    CROSS JOIN (SELECT TOP(@m) v-1 FROM numbers ORDER BY v ASC) m(m)
)

And finally, we put everything together and sum

-- These are the amounts we're working with
, amounts(a) AS
(
SELECT 
    * 
FROM 
    (VALUES 
        (164548.65), (148410.72), (131395.33), (130219.97), (128593.28),  
        (124539.92), (103958.45), (103671.87), (100210.36), ( 99645.42), 
        ( 98848.25), ( 97764.84), ( 97577.03), ( 90067.98), ( 87838.22), 
        ( 86730.85), ( 85508.00), ( 83481.78), ( 82886.95), ( 78588.79) 
    ) AS a(a)
)

-- These are the same amounts, ordered
, ordered_amounts AS
(
SELECT 
    row_number() over (order by a) AS i, a
FROM
    amounts
)

-- Here, we join them with our up_and_down_sequence, group and add
SELECT 
    code, sum(a) AS amount_for_code
FROM 
    ordered_amounts 
    JOIN up_and_down_sequence ON up_and_down_sequence.i = ordered_amounts.i
GROUP BY
    code 
ORDER BY
    code ;

The results are:

code    amount_for_code
1       441631.11
2       429272.87
3       416126.01
4       409754.40
5       427702.27

... which agrees completely with @irimias approach, which I must confess is way shorter and more elegant; but which took me a while to understand. (I'd better learn how to properly use ntile ;-)