Select distinct groups of rows according to average

algorithm, c#-4.0, linq-to-sql, sql-server-2008

Solution

Here is a T-SQL procedural version that is somewhat like a draft, only draft order is optimized each round according to need.

The "competitive" nature of this seems to lead to slightly less than perfect ratios if all items are to be picked, but the up-side is that you basically have an O(N^2) algorithm since it's essentially a min function in a loop (maybe that's optimistic considering the `group by` clauses). It's also deterministic, and should be fairly straightforward to implement in another layer if necessary.

-- SET THESE!
declare @numberOfGroups int = 3
declare @itemsPerGroup int = 25
declare @targetRatio decimal(8,4) = .8
-- /SET

set nocount on

-- Create a table of items
declare @t_stats table (
      id int not null primary key
    , ratio decimal(8,4) not null
    , grp int null
)
insert into @t_stats (id, ratio) values
    (24,0.930000), (25,0.390000), (26,0.800000),
    (27,0.920000), (28,0.550000), (30,0.810000),
    (31,0.770000), (32,0.800000), (33,0.590000),
    (36,0.760000), (37,0.910000), (40,0.690000),
    (43,0.390000), (45,0.310000), (46,0.760000),
    (47,0.710000), (54,0.710000), (55,0.950000),
    (57,0.920000), (60,0.890000), (62,0.700000),
    (66,0.890000), (68,0.950000), (107,0.760000),
    (559,0.990000), (560,0.540000), (565,0.430000),
    (566,0.830000), (568,0.590000), (579,0.970000),
    (599,0.900000), (623,0.450000), (749,0.800000),
    (750,0.970000), (753,0.820000), (754,0.730000),
    (766,0.620000), (768,0.430000), (770,0.790000),
    (838,0.700000), (875,0.835000), (987,0.900000),
    (988,0.740000), (1157,0.850000), (1250,0.630000),
    (1328,0.860000), (2171,0.900000), (2176,0.520000),
    (2177,0.980000), (2178,0.940000), (2180,0.970000),
    (2184,0.990000), (2187,0.950000), (2188,0.940000),
    (2189,0.920000), (2195,0.990000), (2233,0.900000),
    (2234,0.940000), (2235,0.950000), (2240,0.980000),
    (2243,0.920000), (2253,0.900000), (2266,0.530000),
    (2269,0.920000), (2270,0.970000), (2271,0.750000),
    (2272,0.820000), (2275,0.910000), (2277,0.930000),
    (2281,0.690000), (2282,0.710000), (2288,0.840000),
    (2528,0.870000), (2778,0.950000), (2814,0.990000)

-- Create a table of groups
declare @groups table (
    grp int not null primary key identity
)
while (select isnull(max(grp), 0) from @groups) < @numberOfGroups begin
    insert into @groups default values
end

-- Check that we have enough items to fill all groups
if @numberOfGroups * @itemsPerGroup <= (select count(*) from @t_stats) begin

    -- Groups now pick the best-fitting items one at a time
    while (select count(*) from @t_stats where grp is not null) < (select count(*) * @itemsPerGroup from @groups) begin
        declare @grp int, @Num int, @ratio decimal(8,4), @id int

        -- Find the group with the least number of items or the worst ratio
        select top 1 @grp = grp, @Num = Num, @ratio = ratio
        from (
            select g.grp
                , count(i.grp) as Num
                , isnull(avg(i.ratio), 0.0) as ratio
                , abs(@targetRatio - avg(i.ratio)) as RatioDist
            from @groups g
                left join @t_stats i on g.grp = i.grp
            group by g.grp
        ) as a
        order by Num, RatioDist, grp

        -- Let that group make their best pick
        select top 1 @id = id
        from (
            select id
                , abs(((ratio + (@ratio * @Num)) / (@Num + 1)) - @targetRatio) as NewRatioDist
            from @t_stats
            where grp is null
        ) as a
        order by NewRatioDist

        -- Update the items table based upon the pick
        update @t_stats set grp = @grp where id = @id

    end

end
else begin
    -- Not enought items
    raiserror('Too many groups or items per group.', 17, 0)
end

-- Display the results
select grp, count(*) as Num, avg(ratio) as ratio
from @t_stats
group by grp
order by grp

Problem

Original source