从组合表中创建成功的组合

Question

再会，

我希望为我选择的每个科目选择两个对照科目。我得到的开始数据如下：

Cohort  Controls
#a      #1
#a      #2
#a      #3
#a      #4

#b      #1
#b      #2

#c      #5
#c      #6
#c      #1
#c      #2

我想要每个队列主题具有独特控件的结果表，如下所示：

#a      #3
#a      #4
#b      #1
#b      #2
#c      #5
#c      #6

这里有一个问题：需要有逻辑来选择控件，这样我们就不会陷入“死胡同”：如果我们选择.groupby('Cohort').head(2)我们选择组合 A-1 和 A -2 领先领先 B 无比赛。

我通过随机蛮力顺序解决了这个问题，循环每个队列，取 2 并从列表中删除。如果每个队列少于 2 个，则重复。这是缓慢、愚蠢且不可靠的。

如何进行集合魔法“从每组中取出两个，以便每个子集保持唯一（并且没有重叠）”。

Answer 1

输出有多种可能的组合。

groupby.nunique一个简单的启发式（不一定是最佳的）可能是首先通过在 之前进行排序，将重复项保留在具有很少值（用 计数）的组中drop_duplicates：

num = df.groupby('Cohort')['Controls'].nunique()

out = (
 df.sort_values(by='Cohort', key=num.get)
   .drop_duplicates(subset=['Controls'])
)

输出：

  Cohort Controls
4     #b       #1
5     #b       #2
2     #a       #3
3     #a       #4
6     #c       #5
7     #c       #6

更复杂的启发式

在这里，我们计算属于唯一队列的项目并分配它们，然后我们循环剩余的项目并从可能选择数量最少的队列开始逐一分配它们，然后重复直到完成（或卡住）。

这可能并不完美，如果您想要一个适用于所有边缘情况的解决方案，您将需要使用回溯，但它应该（希望）适用于大多数情况。

target = 2

sets1 = df.groupby('Controls')['Cohort'].agg(set)
length = sets1.str.len()
unique = set(sets1[length==1].index)
# {'#3', '#4', '#5', '#6', '#7', '#8'}

sets2 = df.groupby('Cohort')['Controls'].agg(set).to_dict()
# {'#a': {'#1', '#4', '#2', '#3'},
#  '#b': {'#1', '#7', '#2'},
#  '#c': {'#5', '#6', '#1', '#2'},
#  '#d': {'#1', '#8'}}

out = {}
used = set()

sets2 = dict(sorted(sets2.items(), key=lambda x: x[1]))
for k, s in sets2.items():
    # keep up to "target" unique items
    out[k] = {x for i,x in enumerate(s&unique) if i<target}
    used.update(out[k])
    s-=used
    
cont = True
while cont:
    # sorting the cohorts with the least number of remaining choices first
    sets2 = dict(sorted(sets2.items(), key=lambda x: x[1]))
    cont = False
    for k, s in sets2.items():
        if len(out[k]) >= target: # we're done with this key
            continue
        if len(s)>0:
            item = next(iter(s))  # adding one more item
            cont = True
            out[k].add(item)
            used.add(item)
            s -= used

输出：

{'#a': {'#3', '#4'},
 '#b': {'#1', '#7'},
 '#c': {'#5', '#6'},
 '#d': {'#1', '#8'},
 '#e': {'#10', '#9'}}

使用的输入：

   Cohort Controls
0      #a       #1
1      #a       #2
2      #a       #3
3      #a       #4
4      #b       #1
5      #b       #2
6      #b       #7
7      #b      #10
8      #c       #5
9      #c       #6
10     #c       #1
11     #c       #2
12     #c       #9
13     #c      #11
14     #d       #1
15     #d       #8
16     #e       #9
17     #e      #10