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

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.

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.

• To get an exact solution, you need a variant of the (optimization algorithm) for the Partition Problem. In general, this is a rather complicated problem, with some possible approximations. I think your solution is somehow similary to the greedy algorithm. Jan 8, 2017 at 21:52

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.

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` ;-)