谜题：将数字均匀分组
这真的是一个谜题。 它可能在别处被问过，但我找不到任何东西，所以我想我会分享这个问题。
我试图在应用程序中实现某种负载均衡，并将问题简化为我认为应该是简单的TSQL练习（该应用程序主要在SQL Server域（SQL Server 2008 R2））中。
基本上我有一个有两个整数的表格; 唯一的顺序Id和非唯一值。 该表可以包含任意数量的记录，并且我想生成一个数据表，其中前n个最大值分成单独的'分组'，然后第二个n个最大值分成单独的'分组'。
我有第一份草案在下面工作，但我相信它可以改进...
DECLARE @GroupCount INT = 5
-- Set up the test data
DECLARE @test TABLE (Id INT IDENTITY(1, 1), Value INT)
INSERT @Test (Value)
VALUES (100), (456), (121), (402), (253), (872), (765), (6529), (1029), (342), (98), (1), (0), (4), (46), (23), (456), (416), (2323), (4579)
--Order by Value descending
;WITH cte AS
(
SELECT *
,ROW_NUMBER() OVER (ORDER BY Value DESC) RowNum
FROM @Test
)
--use modulus to split into grouping
, cte2 AS
(
SELECT *
,ROW_NUMBER() OVER (PARTITION BY RowNum % @GroupCount ORDER BY RowNum DESC) Rnk
FROM cte
)
SELECT ROW_NUMBER() OVER (PARTITION BY Rnk ORDER BY Value DESC) AS 'Grouping'
,Value
,Id
FROM cte2
ORDER BY [Grouping], Value ASC
这工作并产生以下数据集：
Grouping, Value, Id
======== ===== ==
1 46 15
1 342 10
1 765 7
1 6529 8
2 23 16
2 253 5
2 456 2
2 4579 20
3 4 14
3 121 3
3 456 17
3 2323 19
4 1 12
4 100 1
4 416 18
4 1029 9
5 0 13
5 98 11
5 402 4
5 872 6
返回的数据集是正确的，因为前n个最大值被分割成单独的分组等，但是每个分组中的总值在分组1中与分组5（例如）相比是非常不同的。
当分组和汇总时，我们可以看到非均匀分布：
Grouping, SummedValues
======== ============
1 7682
2 5311
3 2904
4 1546
5 1372
尽可能少的行数如何才能更好地平衡值，以便每个分组的总值更均匀地分布？
这是有缺陷的，但给出示例数据并不可怕。 你的旅费可能会改变。
declare @groupcount int = 5;
create table t (id int identity(1, 1), value int);
insert t values
(100),(456),(121),(402),(253),(872),(765),(6529),(1029),(342)
, (98),(1),(0),(4),(46),(23),(456),(416),(2323),(4579);
;with cte as (
select *
, rn = row_number() over (order by value asc)
, pct = value/sum(value+.0) over()
, target = 1.0 / @groupcount
from t
)
, remaining as (
select id, value, rn
, grp = convert(int,(sum(value) over (order by rn)/sum(value+.0) over())*@groupCount)+1
from cte
)
select
grp = row_number() over (order by sum(value) desc)
, sumValue = sum(value)
from remaining
group by grp
rextester演示：http://rextester.com/UNV61100
结果：
+-----+----------+
| grp | sumValue |
+-----+----------+
| 1 | 6529 |
| 2 | 4579 |
| 3 | 3483 |
| 4 | 2323 |
| 5 | 1901 |
+-----+----------+
Sql Server 2008兼容版本：
declare @groupcount int = 5;
create table t (id int identity(1, 1), value int);
insert t values
(100),(456),(121),(402),(253),(872),(765),(6529),(1029),(342)
, (98),(1),(0),(4),(46),(23),(456),(416),(2323),(4579);
;with cte as (
select *
, rn = row_number() over (order by value asc)
, pct = value/tv.TotalValue
, target = 1.0 / @groupcount
from t
cross join (select TotalValue = sum(value+.0) from t) tv
)
, remaining as (
select id, value, rn
, grp = convert(int,((x.sumValueOver/TotalValue)*@groupcount)+1)
from cte
outer apply (
select sumValueOver = sum(value)
from cte i
where i.rn <= cte.rn
) x
)
select
grp = row_number() over (order by sum(value) desc)
, sumValue = sum(value)
from remaining
group by grp
rextester演示：http://rextester.com/DEUDJ77007
收益：
+-----+----------+
| grp | sumValue |
+-----+----------+
| 1 | 6529 |
| 2 | 4579 |
| 3 | 3483 |
| 4 | 2323 |
| 5 | 1901 |
+-----+----------+
这里sql server中的NTILE函数可以帮助你。
DECLARE @GroupCount INT = 5
-- Set up the test data
DECLARE @test TABLE (Id INT IDENTITY(1, 1), Value INT)
INSERT @Test (Value)
SELECT 100
UNION ALL
SELECT 456
UNION ALL
SELECT 121
UNION ALL
SELECT 402
UNION ALL
SELECT 253
UNION ALL
SELECT 872
UNION ALL
SELECT 765
UNION ALL
SELECT 6529
UNION ALL
SELECT 1029
UNION ALL
SELECT 342
UNION ALL
SELECT 98
UNION ALL
SELECT 1
UNION ALL
SELECT 0
UNION ALL
SELECT 4
UNION ALL
SELECT 46
UNION ALL
SELECT 23
UNION ALL
SELECT 456
UNION ALL
SELECT 416
UNION ALL
SELECT 2323
UNION ALL
SELECT 4579
;With cte
AS
(
SELECT *, NTILE(@GroupCount) OVER(ORDER BY Value DESC) AS GroupNo FROM @Test
)
SELECT GroupNo, SUM(Value) AS SummedValues FROM cte
GROUP BY GroupNo
我得到了这个结果。
GroupNo SummedValues
--------------------
1 14460
2 2549
3 1413
4 365
5 28
做一个稍微好一点的方法是“蛇”选择。 你排在第一，第六和第十一位 - 当然这比第五，第十，第十五位要高。
最好是第一，第十，第十一，第五，第六，第十五。 仍然不完美，并且您的特定数据仍然非常差，但略好于您的数据。
DECLARE @GroupCount INT = 5
-- Set up the test data
DECLARE @test TABLE (Id INT IDENTITY(1, 1), Value INT)
INSERT @Test (Value)
SELECT 100
UNION ALL
SELECT 456
UNION ALL
SELECT 121
UNION ALL
SELECT 402
UNION ALL
SELECT 253
UNION ALL
SELECT 872
UNION ALL
SELECT 765
UNION ALL
SELECT 6529
UNION ALL
SELECT 1029
UNION ALL
SELECT 342
UNION ALL
SELECT 98
UNION ALL
SELECT 1
UNION ALL
SELECT 0
UNION ALL
SELECT 4
UNION ALL
SELECT 46
UNION ALL
SELECT 23
UNION ALL
SELECT 456
UNION ALL
SELECT 416
UNION ALL
SELECT 2323
UNION ALL
SELECT 4579
--Order by Value descending
;WITH cte AS
(
SELECT *
,ROW_NUMBER() OVER (ORDER BY Value DESC) RowNum
FROM @Test
)
--use modulus to split into grouping
, cte2 AS
(
SELECT *
,ROW_NUMBER() OVER (PARTITION BY RowNum % (@GroupCount*2 ) ORDER BY RowNum DESC) Rnk
FROM cte
)
select [Grouping], SUM(value) from (
SELECT floor(abs(@GroupCount - (ROW_NUMBER() OVER (PARTITION BY Rnk ORDER BY Value DESC) - 0.5)) + 0.5) AS 'Grouping'
,Value
,Id
FROM cte2
--ORDER BY [Grouping], Value ASC
) a group by [Grouping]
order by [Grouping] ASC
最终，虽然我认为随机分配可能比这更好，但也许随机分配，而检查总和还不是2 *（1 /分组*总数）。
真的，我认为这不是TSQL或任何SQL很好解决的问题; 可以逐行控制流量的语言将更好地为您服务。 Python，C＃，SAS，以及工具箱中的其他工具。 （PL / SQL是我认为要去的地方...）
任何可以让你在行级基础上说的话，“到目前为止，我已经记录了我已经分配的内容，将这个特定案例分配给目前为止编号最低的数据库”确实会更好。
Grouping Summed Values
---------------------
1 1781
2 1608
3 2904
4 5249
5 7273