找到选择的最佳重分区

Question

我有几个人在n可能性中按偏好排序x选择。每个可能性只能分配一次。

我想找到问题的所有解决方案，这样每个人都可以选择一个最小水平xmin。

例如，对于x=3和n=20，以及10个人做出选择:

g1 = (3, 10, 11)  # g1 makes choices 3, 10 and 11 in order of preference
g2 = (10, 9, 5)
g3 = (10, 15, 3)
g4 = (5, 9, 14)
g5 = (10, 3, 7)
...
g10 = (4, 19, 2)

使用Python，如何编写问题以找到解决方案，以便所有人都有至少分配级别2 (xmin=2)的选择?若xmin=2无解则为三级(xmin=3) ?

我认为这与itertools有关，但是我对这个问题没有一个明确的想法。

编辑仔细想想这个问题，我想到了这样的事情:

import itertools
xmin = 2
groups = [g1, g2, g3, g4, g5]
sample = [g[:xmin] for g in groups]
[seq for seq in itertools.product(*sample) if len(seq) == len(set(seq))]

我没醒，答案其实很简单!

Answer 1

最后，itertools一如既往地简化了生活:)

对于这个数据集:

gr1 = (3, 10, 11)
gr2 = (10, 9, 5)
gr3 = (10, 15, 3)
gr4 = (5, 9, 14)
gr5 = (10, 22, 7)
gr6 = (24, 9, 17)
gr7 = (10, 17, 3)
gr8 = (14, 21, 2)
gr9 = (14, 12, 21)
gr10 = (9, 1, 22)
gr11 = (19, 2, 8)
gr12 = (3, 8, 24)
gr13 = (9, 5, 13)
gr14 = (9, 1, 12)

这个问题的解决方案是:

import itertools
import numpy as np
xmin = 3
groups = [gr1, gr2, gr3, gr4, gr5, gr6, gr7, gr8, gr9, gr10, gr11, gr12, gr13, gr14]

sample = [g[:xmin] for g in groups]
assign = [seq for seq in itertools.product(*sample) if len(seq) == len(set(seq))]
choices = [[sample[i].index(assign[j][i]) for i in range(len(sample))] for j in range(len(assign))]
print(f'{len(choices)} possibilities found')
pertinence = [sum(choices[i]) for i in range(len(choices))]
best = np.array(assign)[np.array(pertinence) == min(pertinence)]
print(f'{len(best)} best choices:')
print(best)         

如果有人有更优雅的解决方案…