1

I have a table of users and values

|---------------------|------------------|
|         User        |       Value      |
|---------------------|------------------|
|          1          |        34        |
|---------------------|------------------|
|          2          |        120       |
|---------------------|------------------|
|          3          |        6         |
|---------------------|------------------|

and I would like to distribute these rows into two groups while minimizing the difference in SUM(Value) between each group. The number of users between the two groups should differ by at most one if initial user count is odd, or be of equal length if the number of initial users is even.

|---------------------|------------------|------------------|
|        Group        |       Users      |    SUM(Value)    |
|---------------------|------------------|------------------|
|          1          |       1,3        |        40        |
|---------------------|------------------|------------------|
|          2          |        2         |       120        |
|---------------------|------------------|------------------|

This should work for any number of users greater than 2. Is there something built-in to Postgres to help with this?

4
  • 2
    Hi and welcome to the forum! In future, could you please provide your table structures as DDL and your table data as DML - possibly as a fiddle. For your own sanity, can I recommend that you never use SQL keywords as variable names? – Vérace Jun 15 '20 at 16:27
  • 2
    Which version of Postgres are you using? Please tag. – Colin 't Hart Jun 15 '20 at 17:16
  • Some ideas here and here which are for SQL Server but may be transferable. – Michael Green Jun 16 '20 at 3:26
  • Related question: dba.stackexchange.com/questions/211510/… – Michael Green Jun 16 '20 at 5:17
1

Only if you count SQL itself :) The DB does not have any way of solving this type of thing other than the naive way, but the naive way of generating all possible distributions of rows to groups, filtering to only those that satisfy the num_users_in_longest<=(num_users_in_shortest+1) requirement, and then calculating the delta for each distribution and using a LIMIT 1 to filter to the smallest one can be expressed in SQL without too much awkwardness. Here's a fiddle that does what you want. Again, this is doing the underlying work in the naive, inefficient way, and this won't scale to large datasets. For that, you'll need to find some clever algorithm to do this, and probably do it in a procedural language that gives you the flow control needed to implement it.

3
  • 1
    Thnx for the answer. I see you have long experience on other sites (SO, ..), just wanting to point out that we prefer the code to be in the answer (besides any fiddle, which is great). – ypercubeᵀᴹ Jun 16 '20 at 1:11
  • 2
    There is also dbfiddle.uk (made an maintained by a former mod of this site), please try it. I personally prefer it over other ones for SQL related stuff. Lots of features and lots of different DBMS. – ypercubeᵀᴹ Jun 16 '20 at 1:13
  • @ypercubeᵀᴹ: well put. db-fiddle.com also executes code from a whole lot of additional sites, which makes me skeptical about its safety. – Erwin Brandstetter Jun 16 '20 at 1:37
1

I can't think of a set-based solution (pure SQL) that can compete with this simple PL/pgSQL function. It produces pretty good results, but fails to deliver the best solution in certain situations. See below.

"Form two groups with equal number of members (or surplus of 1) where the sum of values is as evenly split as possible."

CREATE OR REPLACE FUNCTION f_fair_split()
  RETURNS TABLE (grp int, users int[], sum int)
  LANGUAGE plpgsql AS
$func$
DECLARE
   _id         int;
   _value      int;
   _users1     int[];
   _users2     int[];
   _sum1       int := 0;
   _sum2       int := 0;
   _ct1        int := 0; -- count of members in group 1
   _ct2        int := 0; -- count of members in group 2
   _ct_max     int;      -- current maximum member count
   _ct_limit   int := (SELECT (count(*)::int + 1) / 2 FROM users); -- member limit

BEGIN
   FOR _id, _value IN
      SELECT id, value
      FROM   users
      ORDER  BY value DESC, id  -- id as optional tiebreaker
   LOOP
      -- once one group has maximum members, rest goes to other group
      IF _ct_max >= _ct_limit THEN
         IF _ct1 > _ct2 THEN
            _users2 := _users2 || _id;
            _sum2   := _sum2 + _value;
         ELSE
            _users1 := _users1 || _id;
            _sum1   := _sum1 + _value;
         END IF;
      -- else add to group with lower sum
      ELSE                 
         IF _sum1 > _sum2 THEN
            _users2 := _users2 || _id;
            _sum2   := _sum2 + _value;
            _ct2    := _ct2 + 1; 
         ELSE
            _users1 := _users1 || _id;
            _sum1   := _sum1 + _value;
            _ct1    := _ct1 + 1;
         END IF;

         _ct_max := GREATEST (_ct1, _ct2);  -- keep track of max member count
      END IF;
   END LOOP;
   
   RETURN QUERY VALUES (1, _users1, _sum1), (2, _users2, _sum2);
END
$func$;

Call:

SELECT * FROM f_fair_split();

db<>fiddle here

Assuming both columns NOT NULL.

How?

The function walks through the table sorted by descending value (and id as optional tiebreaker to produce deterministic results), adding to the group with the lower sum so far.

Once the allowed maximum of group members is reached, the rest goes to the other group.

This splits the sum as fair as possible in most cases. There are corner case distributions, where it doesn't produce the best result, though, as ypercube demonstrated with 10,9,8,5,5. And Michael with 10,9,8,5,5,1. It's pretty obvious, too: When the fairest split requires to add the next biggest value to the leading side, the simple algorithm fails.

5
  • Does the algorithm find the best solution in all cases? – ypercubeᵀᴹ Jun 16 '20 at 1:15
  • @ypercubeᵀᴹ: I would think so. But I have no proof to offer. Just what I arrived at after thinking about it. – Erwin Brandstetter Jun 16 '20 at 1:34
  • It's good answer, either case. – ypercubeᵀᴹ Jun 16 '20 at 1:35
  • @ypercubeᵀᴹ: Your example of 10,9,8,5,5 proves me wrong. The function only finds a fairly good solution in this case, not the best. – Erwin Brandstetter Jun 16 '20 at 1:44
  • 2
    10,9,8,5,5,1 has an even number of rows and will produce answer 20,18 whereas the optimal is 19,19. – Michael Green Jun 16 '20 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.