С учетом
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.
Детали
Наивный подход (без предпочтений) с использованием itertools grouper Рецепт:
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']]}
Лучшие варианты на этаже упорядочены слева направо, например Индекс 0 каждого значения в dict указывает кандидатов, которые выбирают этот этаж в качестве предпочтения номер 1. Индекс 2 указывает их предпочтение номер 2 и т. Д. На некоторых этажах есть кандидаты с привязанными предпочтениями (yoder3 и kartz3, по индексу [0]). На некоторых этажах нет предпочтений (miller3 на [0]). Остальная часть логики в preferred_assignments(), то есть переменные a-e, создают комбинации претендентов на основе предпочтений (представьте вертикальные столбцы). Пропущенные значения случайным образом подставляются из оставшегося числа кандидатов.
В демонстрационной версии, поскольку эти комбинации сгруппированы по предпочтениям, мы выравниваем комбинации с помощью itertools.chain.from_iterable() и приводим к набору для удаления любых дубликатов.