SQL – ROW_NUMBER, MOD, Even Distribution

December 9, 2009

A question appeared in the comp.databases.oracle.server Usenet group a couple years ago:
http://groups.google.com/group/comp.databases.oracle.server/browse_thread/thread/41ee30267e646e10

Say I have a bunch of bowling players of different skill level as indicated by his avg_score in the table below.

I need to allot them into n teams (say 8), of equivalent strength on the TEAM level so no team ends up with mostly high-scorers and vic-versa.
(let’s say players may not be evenly divided into teams because n numbers are “sick”)

Is there a way to do to this ?

10gR2> create table players (id integer primary key, avg_score number, team_no integer);

10gR2> desc players
Name      Type
--------- -------
ID        INTEGER
AVG_SCORE NUMBER
TEAM_NO   INTEGER

 

10gR2> BEGIN
  2    FOR i IN 1..120
  3    LOOP
  4        INSERT INTO players (id, avg_score) VALUES(i,round(dbms_random.value(75,295)));
  5    END LOOP;
  6  END ;
  7  /

Needs work, but may be enough to get you started:

SELECT
  ID,
  AVG_SCORE,
  ROW_NUMBER() OVER (ORDER BY AVG_SCORE) RANKING,
  COUNT(*) OVER (PARTITION BY 1) ROWS_COUNT
FROM
  PLAYERS;

        ID  AVG_SCORE    RANKING ROWS_COUNT
---------- ---------- ---------- ----------
        74         78          1        120
        91         82          2        120
        95         83          3        120
        77         86          4        120
        61         87          5        120
        23         87          6        120
         1         90          7        120
        67         91          8        120
        62         97          9        120
        33         98         10        120
...
        88        271        111        120
        41        272        112        120
       104        274        113        120
        32        275        114        120
        36        275        115        120
        99        276        116        120
        71        277        117        120
        31        285        118        120
         3        286        119        120
       113        288        120        120

If we were to take the people at rank 1 and rank 120, they would have roughly the same average as the people at rank 2 and rank 119, and they would have roughly the same average as the people at rank 3 and 118, etc.  This does not work exactly as planned as the number of people must be evenly divisible by 2 * the number of groups, and this is not the case with 120 people and 8 groups.

We can have Oracle skip from 1 to 9 to 17 to … by using the MOD function, but we must recognize the mid-point so that we can switch the formula.

By sliding the above into an inline view, we can perform the analysis that is required.  I included three additional columns to help determine whether or not the formula is close:

SELECT
  ID,
  AVG_SCORE,
  DECODE(SIGN(RANKING-(ROWS_COUNT/2)),-1,MOD(RANKING-1,8)+1,((8-1)-MOD(RANKING-(8/2),8))+1) TEAM_NO,
  RANKING,
  SUM(AVG_SCORE) OVER (PARTITION BY DECODE(SIGN(RANKING-(ROWS_COUNT/2)),-1,MOD(RANKING-1,8)+1,((8-1)-MOD(RANKING-(8/2),8))+1)) TEAM_AVG,
  COUNT(*) OVER (PARTITION BY DECODE(SIGN(RANKING-(ROWS_COUNT/2)),-1,MOD(RANKING-1,8)+1,((8-1)-MOD(RANKING-(8/2),8))+1)) NUM_TEAM_MEMBERS
FROM
  (SELECT
    ID,
    AVG_SCORE,
    ROW_NUMBER() OVER (ORDER BY AVG_SCORE) RANKING,
    COUNT(*) OVER (PARTITION BY 1) ROWS_COUNT
  FROM
    PLAYERS)
ORDER BY
  RANKING;

        ID  AVG_SCORE    TEAM_NO    RANKING   TEAM_AVG NUM_TEAM_MEMBERS
---------- ---------- ---------- ---------- ---------- ----------------
        74         78          1          1       2603 15
        91         82          2          2       2602 15
        95         83          3          3       2592 15
        77         86          4          4       2709 15
        61         87          5          5       2701 15
        23         87          6          6       2690 15
         1         90          7          7       2686 15
        67         91          8          8       2689 15
        62         97          1          9       2603 15
        33         98          2         10       2602 15
        79         98          3         11       2592 15
       120        100          4         12       2709 15
         2        101          5         13       2701 15
        39        101          6         14       2690 15
        60        102          7         15       2686 15
       101        104          8         16       2689 15
...
        14        257          8        108       2689 15
        59        259          7        109       2686 15
        29        262          6        110       2690 15
        88        271          5        111       2701 15
        41        272          4        112       2709 15
       104        274          3        113       2592 15
        32        275          2        114       2602 15
        36        275          1        115       2603 15
        99        276          8        116       2689 15
        71        277          7        117       2686 15
        31        285          6        118       2690 15
         3        286          5        119       2701 15
       113        288          4        120       2709 15