python - Python - 有效地从两个字典中获取所有可能的组合
问题描述
ra_position_preferences = {"yoder3":["J","E","T","S","M","R","B","SS"],
"yoder4":["J","E","S","T","M","R","SS","B"],
"kratz3":["M","J","S","E","T","R","B","SS"],
"miller3":["S","M","J","E","T","R","B","SS"],
"nofloor":["SS","B","R","T","S","M","E","J"]}
applicants_floor_prefernce ={"J":["yoder3","yoder4","kratz3","miller3","nofloor"],
"E":["yoder3","yoder4","kratz3","miller3","nofloor"],
"S":["kratz3","miller3","yoder3","yoder4","nofloor"],
"M":["kratz3","miller3","nofloor","yoder3","yoder4"],
"T":["nofloor","yoder4","yoder3","kratz3","miller3",],
'SS':["yoder3","yoder4","kratz3","miller3","nofloor"],
'R':["kratz3","miller3","yoder3","yoder4","nofloor"],
'B':["yoder4","yoder3","kratz3","miller3","nofloor"]}
在上述字典中,所有值都是键的首选项。就像匹配问题https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf一样。我试图在这里获得所有可能的偏好组合,而不会出现内存错误。此外,我将我得到的每一个组合都放入大风沙普利算法中,以获得所有可能的匹配。我的代码如下:
def sensitivity_analysis(dic1,dic2): #gives all the possible combinations of the preferences
a=copy.deepcopy(dic1)
b=copy.deepcopy(dic2)
length_a=len(a.keys())
length_b=len(b.keys())
items_a=list(a.keys())
items_b=list(b.keys())
a_variants = [dict(zip(items_a, values))
for values in product(permutations(items_b), repeat=length_a)]
b_variants = [dict(zip(items_b, values))
for values in product(permutations(items_a), repeat=length_b)]
all_variants = product(a_variants, b_variants)
contains_a=[]
contains_b=[]
for i,j in all_variants:
contains_a.append(i)
contains_b.append(j)
return contains_a,contains_b
从上面的代码中,我得到了内存错误。还有其他方法吗?我的建议是一次获得一个组合并将其插入 gale-shapley 函数并获得匹配。然后将匹配项附加到字典中。如果新匹配与上一个相同,我们可以删除新匹配以节省数组中的内存。但仍将是 2.78 亿次计算。你们有什么有效的方法来做到这一点,以便我可以在具有 16 GB RAM 的计算机上运行它吗?
解决方案
给定
import itertools as it
import collections as ct
floors = ["yoder3", "yoder6", "kratz3", "miller3", "nofloor"]
applicants = ["SS", "M", "J", "T", "R", "B", "E", "S"]
preferences = {
"J": ["yoder3", "yoder6", "kratz3", "miller3", "nofloor"],
"E": ["yoder3", "yoder6", "kratz3", "miller3", "nofloor"],
"S": ["kratz3", "miller3", "yoder3", "yoder6", "nofloor"],
"M": ["kratz3", "miller3", "nofloor", "yoder3", "yoder6"],
"T": ["nofloor", "yoder6", "yoder3", "kratz3", "miller3"],
"SS": ["yoder3", "yoder6", "kratz3", "miller3", "nofloor"],
"R": ["kratz3", "miller3", "yoder3", "yoder6", "nofloor"],
"B": ["yoder6", "yoder3", "kratz3", "miller3", "nofloor"]
}
辅助函数
def fill_missing(iterable, fillvalues):
"""Yield combinations replacing empty strings in iterable with fillvalues."""
iter_fillvalues = map(iter, fillvalues)
for x in iter_fillvalues:
comb = []
for item in iterable:
if item == "":
comb.append(next(x))
else:
comb.append(item)
yield comb
代码
def ranked_preferences(floors, preferences):
"""Return a dict of preferences."""
ranked = ct.defaultdict(list)
for floor in floors:
for i in range(len(floors)):
idx_prefs = [
name for name, lst in preferences.items()
for j, v in enumerate(lst) if (j == i and v == floor)
]
if not idx_prefs:
idx_prefs = [""]
ranked[floor].append(idx_prefs)
return dict(ranked)
def preferred_assignments(ranked, applicants, top=None):
"""Yield combinations of preferred assignments."""
if top is None:
top = len(ranked)
applicants = set(applicants)
ranks = zip(ranked.values())
for i, rank in enumerate(ranks):
if i >= top:
continue
for a in it.product(*rank[0]):
missing = a.count("")
b = applicants - set(a)
c = list(it.combinations(b, missing))
d = list(it.chain.from_iterable([list(it.permutations(x, missing)) for x in c]))
e = list(fill_missing(a, d))
yield tuple(tuple(zip(*x)) for x in zip(it.repeat(list(ranked.keys())), e))
演示
根据偏好产生所有组合:
ranked = ranked_preferences(floors, preferences)
combos = set(it.chain.from_iterable(preferred_assignments(ranked, applicants)))
print("Number of preferred combinations:", len(combos))
# Number of preferred combinations: 668
指定top
首选选择:
combos = set(it.chain.from_iterable(preferred_assignments(ranked, applicants, top=1)))
print("Number of preferred combinations:", len(combos))
combos
# Number of preferred combinations: 36
# {(('yoder3', 'E'),
# ('yoder6', 'B'),
# ('kratz3', 'R'),
# ('miller3', 'M'),
# ('nofloor', 'J')),
# (('yoder3', 'E'),
# ('yoder6', 'B'),
# ('kratz3', 'R'),
# ('miller3', 'M'),
# ('nofloor', 'S')),
# (('yoder3', 'E'),
# ...)}
这里只给出了第 1 个选项的组合。您可以通过设置选择前 2 个选项top=2
。
细节
使用 itertoolsgrouper
配方的幼稚方法(没有偏好):
def all_assignments(chunks):
"""Yield all combinations of floors assigned to applicants."""
combs = it.product(*chunks)
for comb in combs:
names = {c[1] for c in comb}
if len(names) != len(floors):
continue
yield comb
chunks_by_floor = list(grouper(len(applicants), it.product(floors, applicants)))
chunks_by_floor[:2]
result = list(all_assignments(chunks_by_floor))
print("Number of combinations:", len(result))
# Number of combinations: 6720
因此,具有偏好的组合是这些组合的某个子集。要选择这个子集,让我们看看按前 1-5 个选项分组的每个楼层的偏好:
ranked
{'yoder3': [['J', 'E', 'SS'], ['B'], ['S', 'T', 'R'], ['M'], ['']],
'yoder6': [['B'], ['J', 'E', 'T', 'SS'], [''], ['S', 'R'], ['M']],
'kratz3': [['S', 'M', 'R'], [''], ['J', 'E', 'SS', 'B'], ['T'], ['']],
'miller3': [[''], ['S', 'M', 'R'], [''], ['J', 'E', 'SS', 'B'], ['T']],
'nofloor': [['T'], [''], ['M'], [''], ['J', 'E', 'S', 'SS', 'R', 'B']]}
每个楼层的最佳选择从左到右排序,例如 dict 中每个值的索引 0 表示选择该楼层作为其第一优先选择的申请人。索引 2 表示他们的 2 号偏好等。一些楼层的申请人具有相同的偏好(yoder3
和kartz3
,在索引处[0]
)。有些楼层没有偏好(miller3
在[0]
)。中的其余逻辑preferred_assignments()
,即变量a-e
,根据偏好组合申请者(想想垂直列)。从剩余的申请人池中随机替换缺失值。
在演示中,由于这些组合是根据偏好分组的,我们将组合扁平化itertools.chain.from_iterable()
并转换为一个集合以删除任何重复项。
推荐阅读
- julia - 使用特殊字符“>”在 Julia 中运行外部程序
- android - 如何更有效地更新 UI
- google-earth-engine - monthlyRainfall.filter(...).first 不是函数
- r - R:根据其他数据框动态定义值范围
- flutter - 如何在颤动中禁用 ForceDark
- javascript - 尝试借助 Vuejs 中的列表和网格视图中的分页显示数据时出现问题?
- python - Qiskit-Textbook 是在哪里下载的?
- visual-studio - 分析服务视觉工作室中的错误
- python - 使用 Python 从 Google 工作表中的特定行(一次)获取数据
- android - 我的默认拨号应用程序被拒绝了很多次,因为我正在使用读取通话记录权限