Я пытаюсь реализовать алгоритм, чтобы найти все стабильные брачные решения с использованием подхода грубой силы без алгоритма Гейла-Шепли (потому что он дает нам только 2 из них).Я использую механизм проверки, найденный в rosettacoode , но мне трудно найти способ создать все возможные совпадения без повторений (тот, который у вас есть с 2 для циклов), например
from these 2 lists [a,b,c] and [d,e,f] create
[(a,d),(b,e),(c,f)]
[(a,d),(b,f),(c,e)]
[(a,e),(b,f),(c,d)]
[(a,e),(b,d),(c,f)]
[(a,f),(b,d),(c,e)]
[(a,f),(b,e),(c,d)]
ОБНОВЛЕНИЕ 1: Со всеми решениями до сих пор я не могу запустить его, когда он станет большим.Я, вероятно, должен делать это рекурсивно, не сохраняя длинные структуры данных, тестируя единственный результат, когда получаю его, и отбрасывая остальные.Я вышел с этим решением, но все еще есть проблемы, потому что дает мне некоторое повторение и то, чего не хватает.Я не знаю, как это исправить, и извините, мой мозг тает!
boys=['a','b','c']
girls=['d','e','f']
def matches(boys, girls, dic={}):
if len(dic)==3: #len(girls)==0 geves me more problems
print dic #just for testing with few elements
#run the stability check
else:
for b in boys:
for g in girls:
dic[b]=g
bb=boys[:]
bb.remove(b)
gg=girls[:]
gg.remove(g)
matches(bb,gg, dic)
dic.clear()
matches(boys,girls)
дает мне этот вывод
{'a': 'd', 'c': 'f', 'b': 'e'} <-
{'a': 'e', 'c': 'f', 'b': 'd'} <-
{'a': 'f', 'c': 'e', 'b': 'd'}
{'a': 'e', 'c': 'f', 'b': 'd'} <-
{'a': 'd', 'c': 'f', 'b': 'e'} <-
{'a': 'd', 'c': 'e', 'b': 'f'} <-
{'a': 'e', 'c': 'd', 'b': 'f'}
{'a': 'd', 'c': 'e', 'b': 'f'} <-
{'a': 'd', 'c': 'f', 'b': 'e'} <-
ОБНОВЛЕНИЕ 2 Моя полная работаупражнение, вдохновленное @Zags (вдохновлено @Jonas):
guyprefers = {
'A': ['P','S','L','M','R','T','O','N'],
'B': ['M','N','S','P','O','L','T','R'],
'D': ['T','P','L','O','R','M','N','S'],
'E': ['N','M','S','O','L','R','T','P'],
'F': ['S','M','P','L','N','R','T','O'],
'G': ['L','R','S','P','T','O','M','N'],
'J': ['M','P','S','R','N','O','T','L'],
'K': ['N','T','O','P','S','M','R','L']
}
galprefers = {
'L': ['F','D','J','G','A','B','K','E'],
'M': ['K','G','D','F','J','B','A','E'],
'N': ['A','F','G','B','E','K','J','D'],
'O': ['K','J','D','B','E','A','F','G'],
'P': ['G','E','J','D','K','A','B','F'],
'R': ['B','K','F','D','E','G','J','A'],
'S': ['J','F','B','A','K','G','E','D'],
'T': ['J','E','A','F','B','D','G','K']
}
guys = sorted(guyprefers.keys())
gals = sorted(galprefers.keys())
def permutations(iterable): #from itertools a bit simplified
pool = tuple(iterable) #just to understand what it is doing
n = len(pool)
indices = range(n)
cycles = range(n, 0, -1)
while n:
for i in reversed(range(n)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:n])
break
else:
return
def check(engaged): #thanks to rosettacode
inversengaged = dict((v,k) for k,v in engaged.items())
for she, he in engaged.items():
shelikes = galprefers[she]
shelikesbetter = shelikes[:shelikes.index(he)]
helikes = guyprefers[he]
helikesbetter = helikes[:helikes.index(she)]
for guy in shelikesbetter:
guysgirl = inversengaged[guy]
guylikes = guyprefers[guy]
if guylikes.index(guysgirl) > guylikes.index(she):
return False
for gal in helikesbetter:
girlsguy = engaged[gal]
gallikes = galprefers[gal]
if gallikes.index(girlsguy) > gallikes.index(he):
return False
return True
match_to_check={}
for i in permutations(guys):
couples = sorted(zip(i, gals))
for couple in couples:
match_to_check[couple[1]]=couple[0]
if check(match_to_check):
print match_to_check
match_to_check.clear()
с правильным выводом:
{'M': 'F', 'L': 'D', 'O': 'K', 'N': 'A', 'P': 'G', 'S': 'J', 'R': 'B', 'T': 'E'}
{'M': 'F', 'L': 'D', 'O': 'K', 'N': 'B', 'P': 'G', 'S': 'J', 'R': 'E', 'T': 'A'}
{'M': 'J', 'L': 'D', 'O': 'K', 'N': 'A', 'P': 'G', 'S': 'F', 'R': 'B', 'T': 'E'}
{'M': 'J', 'L': 'D', 'O': 'K', 'N': 'B', 'P': 'G', 'S': 'F', 'R': 'E', 'T': 'A'}
{'M': 'D', 'L': 'F', 'O': 'K', 'N': 'A', 'P': 'G', 'S': 'J', 'R': 'B', 'T': 'E'}
{'M': 'J', 'L': 'G', 'O': 'K', 'N': 'A', 'P': 'D', 'S': 'F', 'R': 'B', 'T': 'E'}
{'M': 'J', 'L': 'G', 'O': 'K', 'N': 'B', 'P': 'A', 'S': 'F', 'R': 'E', 'T': 'D'}
{'M': 'J', 'L': 'G', 'O': 'K', 'N': 'B', 'P': 'D', 'S': 'F', 'R': 'E', 'T': 'A'}