Postgresql – Distribute rows into groups while minimizing difference

postgresql

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?

Best Answer

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.

Related Solutions

PostgreSQL – How to Find Consecutive Free Numbers Using Window Functions

This is a gaps-and-islands problem. Assuming there are no gaps or duplicates in the same id_set set:

WITH partitioned AS (
  SELECT
    *,
    number - ROW_NUMBER() OVER (PARTITION BY id_set) AS grp
  FROM atable
  WHERE status = 'FREE'
),
counted AS (
  SELECT
    *,
    COUNT(*) OVER (PARTITION BY id_set, grp) AS cnt
  FROM partitioned
)
SELECT
  id_set,
  number
FROM counted
WHERE cnt >= 3
;

Here's a SQL Fiddle demo^* link for this query: http://sqlfiddle.com/#!1/a2633/1.

UPDATE

To return only one set, you could add in one more round of ranking:

WITH partitioned AS (
  SELECT
    *,
    number - ROW_NUMBER() OVER (PARTITION BY id_set) AS grp
  FROM atable
  WHERE status = 'FREE'
),
counted AS (
  SELECT
    *,
    COUNT(*) OVER (PARTITION BY id_set, grp) AS cnt
  FROM partitioned
),
ranked AS (
  SELECT
    *,
    RANK() OVER (ORDER BY id_set, grp) AS rnk
  FROM counted
  WHERE cnt >= 3
)
SELECT
  id_set,
  number
FROM ranked
WHERE rnk = 1
;

Here's a demo for this one too: http://sqlfiddle.com/#!1/a2633/2.

If you ever need to make it one set per id_set, change the RANK() call like this:

RANK() OVER (PARTITION BY id_set ORDER BY grp) AS rnk

Additionally, you could make the query return the smallest matching set (i.e. first try to return the first set of exactly three consecutive numbers if it exists, otherwise four, five etc.), like this:

RANK() OVER (ORDER BY cnt, id_set, grp) AS rnk

or like this (one per id_set):

RANK() OVER (PARTITION BY id_set ORDER BY cnt, grp) AS rnk

_{* The SQL Fiddle demos linked in this answer use the 9.1.8 instance as the 9.2.1 one doesn't appear to be working at the moment.}

PostgreSQL – How to Connect to Remote EC2 Database

You need to work your way up the networking stack to determine where the issue is.

Can you ping the destination from the source?

Can you telnet to the postgres port(5432 by default) from the source?

Can you connect to the postgres service with a management tool(pgadmin or psql) from the source?

Best Answer

Related Solutions

PostgreSQL – How to Find Consecutive Free Numbers Using Window Functions

PostgreSQL – How to Connect to Remote EC2 Database

Related Question