Seleccionar datos divididos en grupos distribuidos uniformemente por valor

Me gustaría seleccionar en 4 grupos los datos de una tabla que tenga la suma de valores en los grupos lo más distribuidos posible. Estoy seguro de que no lo estoy explicando lo suficientemente claro, así que intentaré dar un ejemplo.

Aquí uso NTILE (4) para crear los 4 grupos:

SELECT Time, NTILE(4) OVER (ORDER BY Time DESC) AS N FROM TableX

Time -  N
-------------
10  -   1
 9  -   2
 8  -   3
 7  -   4
 6  -   1
 5  -   2
 4  -   3
 3  -   4
 2  -   1
 1  -   2

En la consulta y el resultado anteriores, las otras columnas se han omitido por brevedad.

Para que pueda ver los grupos también de la siguiente manera:

  1    2    3    4
---  ---  ---  ---
 10    9    8    7
  6    5    4    3
  2    1    
---  ---  ---  ---
 18   15   12   10  Sum Totals of Time

Observe que la suma total de tiempo usando NTile no está realmente equilibrada entre los grupos. Una mejor distribución de los valores de tiempo sería, por ejemplo:

  1    2    3    4
---  ---  ---  ---
 10    9    8    7
  3    5    4    6
  1         2
---  ---  ---  ---
 14   14   14   13  Sum Totals of Time

Aquí la suma total de tiempo se distribuye más uniformemente en los 4 grupos.

¿Cómo puedo realizar esto a través de declaraciones TSQL?

Además, debo decir que estoy usando SQL Server 2012. Si tiene algo que pueda ayudarme, avíseme.

Te deseo un buen día.

Stan

Aquí hay una puñalada en un algoritmo. No es perfecto, y dependiendo de cuánto tiempo quieras dedicar a refinarlo, es probable que se realicen algunas pequeñas ganancias adicionales.

Supongamos que tiene una tabla de tareas que deben realizar cuatro colas. Usted sabe la cantidad de trabajo asociado con la realización de cada tarea, y desea que las cuatro colas obtengan una cantidad de trabajo casi igual, por lo que todas las colas se completarán aproximadamente al mismo tiempo.

En primer lugar, dividiría las tareas usando un módulo, ordenado por su tamaño, de pequeño a grande.

SELECT [time], ROW_NUMBER() OVER (ORDER BY [time])%4 AS grp, 0

Las ROW_NUMBER()órdenes de cada fila por tamaño, a continuación, asigna un número de fila, comenzando en 1. Este número de fila se asigna un "grupo" (la grpcolumna) sobre una base round-robin. La primera fila es el grupo 1, la segunda fila es el grupo 2, luego el 3, el cuarto obtiene el grupo 0, y así sucesivamente.

time ROW_NUMBER() grp
---- ------------ ---
   1            1   1
  10            2   2
  12            3   3
  15            4   0
  19            5   1
  22            6   2
...

Para facilitar su uso, estoy almacenando las columnas timey grpen una variable de tabla llamada @work.

Ahora, podemos realizar algunos cálculos sobre estos datos:

WITH cte AS (
    SELECT *, SUM([time]) OVER (PARTITION BY grp)
             -SUM([time]) OVER (PARTITION BY (SELECT NULL))/4 AS _grpoffset
    FROM @work)
...

La columna _grpoffsetes cuánto difiere el total timepor grpel promedio "ideal". Si el total timede todas las tareas es 1000 y hay cuatro grupos, idealmente debería haber un total de 250 en cada grupo. Si un grupo contiene un total de 268, ese grupo es _grpoffset=18.

La idea es identificar las dos mejores filas, una en un grupo "positivo" (con demasiado trabajo) y otra en un grupo "negativo" (con muy poco trabajo). Si podemos intercambiar grupos en esas dos filas, podríamos reducir el absoluto _grpoffsetde ambos grupos.

Ejemplo:

time grp total _grpoffset
---- --- ----- ----------
   3   1   222         40
  46   1   222         40
  73   1   222         40
 100   1   222         40
   6   2   134        -48
  52   2   134        -48
  76   2   134        -48
  11   3   163        -21
  66   3   163        -21
  86   3   163        -21
  45   0   208         24
  71   0   208         24
  92   0   208         24
----
=727

Con un gran total de 727, cada grupo debe tener un puntaje de aproximadamente 182 para que la distribución sea perfecta. La diferencia entre el puntaje del grupo y 182 es lo que estamos poniendo en la _grpoffsetcolumna.

Como puede ver ahora, en el mejor de los mundos, deberíamos mover unos 40 puntos de filas del grupo 1 al grupo 2 y unos 24 puntos del grupo 3 al grupo 0.

Aquí está el código para identificar esas filas candidatas:

    SELECT TOP 1 pos._row AS _pos_row, pos.grp AS _pos_grp,
                 neg._row AS _neg_row, neg.grp AS _neg_grp
    FROM cte AS pos
    INNER JOIN cte AS neg ON
        pos._grpoffset>0 AND
        neg._grpoffset<0 AND
        --- To prevent infinite recursion:
        pos.moved<4 AND
        neg.moved<4
    WHERE --- must improve positive side's offset:
          ABS(pos._grpoffset-pos.[time]+neg.[time])<=pos._grpoffset AND
          --- must improve negative side's offset:
          ABS(neg._grpoffset-neg.[time]+pos.[time])<=ABS(neg._grpoffset)
    --- Largest changes first:
    ORDER BY ABS(pos.[time]-neg.[time]) DESC
    ) AS x ON w._row IN (x._pos_row, x._neg_row);

Me estoy uniendo a la expresión de tabla común que creamos antes cte: por un lado, grupos con positivo _grpoffset, en el otro lado grupos con negativos. Para filtrar aún más qué filas se supone que deben coincidir entre sí, el intercambio de las filas de los lados positivo y negativo debe mejorar _grpoffset, es decir, acercarlo a 0.

El TOP 1y ORDER BYselecciona la "mejor" coincidencia para intercambiar primero.

Ahora, todo lo que tenemos que hacer es agregar un UPDATEy hacer un bucle hasta que no se encuentre más optimización.

TL; DR: aquí está la consulta

Aquí está el código completo:

DECLARE @work TABLE (
    _row    int IDENTITY(1, 1) NOT NULL,
    [time]  int NOT NULL,
    grp     int NOT NULL,
    moved   tinyint NOT NULL,
    PRIMARY KEY CLUSTERED ([time], _row)
);

WITH cte AS (
    SELECT 0 AS n, CAST(1+100*RAND(CHECKSUM(NEWID())) AS int) AS [time]
    UNION ALL
    SELECT n+1,    CAST(1+100*RAND(CHECKSUM(NEWID())) AS int) AS [time]
    FROM cte WHERE n<100)

INSERT INTO @work ([time], grp, moved)
SELECT [time], ROW_NUMBER() OVER (ORDER BY [time])%4 AS grp, 0
FROM cte;



WHILE (@@ROWCOUNT!=0)
    WITH cte AS (
        SELECT *, SUM([time]) OVER (PARTITION BY grp)
                 -SUM([time]) OVER (PARTITION BY (SELECT NULL))/4 AS _grpoffset
        FROM @work)

    UPDATE w
    SET w.grp=(CASE w._row
               WHEN x._pos_row THEN x._neg_grp
               ELSE x._pos_grp END),
        w.moved=w.moved+1
    FROM @work AS w
    INNER JOIN (
        SELECT TOP 1 pos._row AS _pos_row, pos.grp AS _pos_grp,
                     neg._row AS _neg_row, neg.grp AS _neg_grp
        FROM cte AS pos
        INNER JOIN cte AS neg ON
            pos._grpoffset>0 AND
            neg._grpoffset<0 AND
            --- To prevent infinite recursion:
            pos.moved<4 AND
            neg.moved<4
        WHERE --- must improve positive side's offset:
              ABS(pos._grpoffset-pos.[time]+neg.[time])<=pos._grpoffset AND
              --- must improve negative side's offset:
              ABS(neg._grpoffset-neg.[time]+pos.[time])<=ABS(neg._grpoffset)
        --- Largest changes first:
        ORDER BY ABS(pos.[time]-neg.[time]) DESC
        ) AS x ON w._row IN (x._pos_row, x._neg_row);