I'm trying to implement an algorithm to find all stable marriage solutions with a brute force approach without the Gale-Shapley algorithm (because it gives us only 2 of them). I'm using the checking mechanism found in rosettacoode but I'm having an hard time trying to find a way to create all possible matches with no repetitions (the kind you have with 2 for cycles) e.g
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)]
UPDATE1: With all the solutions so far I'm not able to run it when it gets big. I should probably do it recursively without storing long data structures, testing the single result when I get it and discard the others . I came out with this solution but still has problems because gives me some repetition and something that is missing. I don't know how to fix it, and sorry my brain is melting!
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)
gives me this output
{'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'} <-
UPDATE 2 My complete working exercise inspired by @Zags (inspired by @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()
with the correct output:
{'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'}
(Insipred by @Jonas but doesn't require Numpy):
from itertools import permutations
l1 = ["a", "b", "c"]
l2 = ["d", "e", "f"]
valid_pairings = [sorted(zip(i, l2)) for i in permutations(l1)]
valid_pairings is:
[
[('a', 'd'), ('b', 'e'), ('c', 'f')],
[('a', 'd'), ('b', 'f'), ('c', 'e')],
[('a', 'e'), ('b', 'd'), ('c', 'f')],
[('a', 'f'), ('b', 'd'), ('c', 'e')],
[('a', 'e'), ('b', 'f'), ('c', 'd')],
[('a', 'f'), ('b', 'e'), ('c', 'd')]
]
Warning: the size of the output is factiorial(n), where n is the size of one the smaller input. At n = 14, this requires 100's of GBs of memory to store, more than most modern systems have.
from itertools import product, combinations
def flatten(lst):
return [item for sublist in lst for item in sublist]
l1 = ["a", "b", "c"]
l2 = ["d", "e", "f"]
all_pairings = combinations(product(l1, l2), min(len(l1), len(l2)))
# remove those pairings where an item appears more than once
valid_pairings = [i for i in all_pairings if len(set(flatten(i))) == len(flatten(i))]
Valid pairings is:
[
(('a', 'd'), ('b', 'e'), ('c', 'f')),
(('a', 'd'), ('b', 'f'), ('c', 'e')),
(('a', 'e'), ('b', 'd'), ('c', 'f')),
(('a', 'e'), ('b', 'f'), ('c', 'd')),
(('a', 'f'), ('b', 'd'), ('c', 'e')),
(('a', 'f'), ('b', 'e'), ('c', 'd'))
]