给定属于多个组的行，将每一行分配给一个组，其中每个组都有一个限制大小，最大化分组行

Question

我正在寻找这个问题的通用psuedo代码numpy、pandas或sql解决方案

问题陈述： 您有一个具有组列的唯一项表，该列可以属于一个或多个组。将每行仅分配给一个组，同时尝试最大化所有组的总大小。但每组不能超过规定的尺寸。表中的总行数可能大于所有组大小限制的总和，因此需要丢弃某些行

Example Input:
ID   Groups
(4, [s1, s2])
(5, [s1, s2])
(6, [s1])
(15, [s1])
(7, [s2])
(8, [s3])
(10, [s3])
(12, [s3])
(13, [s3])

Desired Output Example
Group 1 (size_limit=3): 5, 6, 15
Group 2 (size_limit=2): 4, 7
Group 3 (size_limit=2): 10, 8


Bad Output
Group 1 (size_limit=3): 4, 5, 6
Group 2 (size_limit=2): 7
Group 3 (size_limit=2): 10, 8

Answer 1

以下是我对解决方案的想法，但不确定它是否涵盖所有情况

SOLUTION

FOR EACH group: sort by samples belonging to the most groups. 
WHILE len(samples for group) > limit): remove group from groups
WHILE samples for group contains samples with more than 1 group: Remove other groups from sample

EXAMPLE INPUT 1:
Group 1 (size_limit=3): 4, 5, 6, 15
Group 2 (size_limit=2): 4, 5, 7
Group 3 (size_limit=2): 8, 10, 12, 13

or

ID  Groups
(4,  [s1, s2])
(5,  [s1, s2])
(6,  [s1])
(15, [s1])
(7,  [s2])
(8,  [s3])
(10, [s3])
(12, [s3])
(13, [s3])

Bad Output Example
Group 1 (size_limit=3): 4, 5, 6
Group 2 (size_limit=2): 7
Group 3 (size_limit=2): 8, 10

Possible Desired Output
Group 1 (size_limit=3): 5, 6, 15
Group 2 (size_limit=2): 4, 7
Group 3 (size_limit=2): 8, 10



For Group 1 (s1)
Group 1 (size_limit=3): 5, 6, 15
Group 2 (size_limit=2): 4, 5, 7
Group 3 (size_limit=2): 8, 10, 12, 13

or

ID  Groups
(4,  [s2])
(5,  [s1, s2])
(6,  [s1])
(15, [s1])
(7,  [s2])
(8,  [s3])
(10, [s3])
(12, [s3])
(13, [s3])

Then remove other groups for group (s1)
Group 1 (size_limit=3): 5, 6, 15
Group 2 (size_limit=2): 4, 7
Group 3 (size_limit=2): 8, 10, 12, 13

or

ID  Groups
(4,  [s2])
(5,  [s1])
(6,  [s1])
(15, [s1])
(7,  [s2])
(8,  [s3])
(10, [s3])
(12, [s3])
(13, [s3])

For group (s2), skip already at limit

For group (s3)
Group 1 (size_limit=3): 5, 6, 15
Group 2 (size_limit=2): 4, 7
Group 3 (size_limit=2): 8, 10

or

ID  Groups
(4,  [s2])
(5,  [s1])
(6,  [s1])
(15, [s1])
(7,  [s2])
(8,  [s3])
(10, [s3])











EXAMPLE 2:
Group 1 (size_limit=3): 4, 5, 6, 7, 8, 9
Group 2 (size_limit=2): 4, 5, 10, 11
Group 3 (size_limit=2): 4, 5, 6

or

ID  Groups
(4,  [s1, s2, s3])
(5,  [s1, s2, s3])
(6,  [s1, s3])
(7,  [s1])
(8,  [s1])
(9,  [s1])
(10, [s2])
(11, [s2])

Group = Group 1 (s1)
Group 1 (size_limit=3): 7, 8, 9
Group 2 (size_limit=2): 4, 5, 10, 11
Group 3 (size_limit=2): 4, 5, 6

or

(4,  [s2, s3])
(5,  [s2, s3])
(6,  [s3])
(7,  [s1])
(8,  [s1])
(9,  [s1])
(10, [s2])
(11, [s2])

Group = Group 2 (s2)
Group 1 (size_limit=3): 7, 8, 9
Group 2 (size_limit=2): 10, 11
Group 3 (size_limit=2): 4, 5, 6

or

(4,  [s3])
(5,  [s3])
(6,  [s3])
(7,  [s1])
(8,  [s1])
(9,  [s1])
(10, [s2])
(11, [s2])

Group = Group 3 (s3)
Group 1 (size_limit=3): 7, 8, 9
Group 2 (size_limit=2): 10, 11
Group 3 (size_limit=2): 5, 6

or

(5,  [s3])
(6,  [s3])
(7,  [s1])
(8,  [s1])
(9,  [s1])
(10, [s2])
(11, [s2])


EXAMPLE 3:
Group = Group 1 (s1)
Group 1 (size_limit=3): 5, 6, 7, 8
Group 2 (size_limit=2): 4, 5, 10, 11
Group 3 (size_limit=2): 4, 5, 6

or

(4,  [s2, s3])
(5,  [s1, s2, s3])
(6,  [s1, s3])
(7,  [s1])
(8,  [s1])
(10, [s2])
(11, [s2])

FOR EACH GROUP


Group = Group 1 (s1)
Group 1 (size_limit=3): 6, 7, 8
Group 2 (size_limit=2): 4, 5, 10, 11
Group 3 (size_limit=2): 4, 5

or

(4,  [s2, s3])
(5,  [s2, s3])
(6,  [s1])
(7,  [s1])
(8,  [s1])
(10, [s2])
(11, [s2])

Group = Group 2 (s2)
Group 1 (size_limit=3): 6, 7, 8
Group 2 (size_limit=2): 10, 11
Group 3 (size_limit=2): 4, 5

or

(4,  [s2])
(5,  [s2])
(6,  [s1])
(7,  [s1])
(8,  [s1])
(10, [s2])
(11, [s2])