暴力稳定婚姻，如何实现 2 个列表之间所有可能的配对？
Brute force stable marriage, How to implements all possible pairs between 2 lists?
我正在尝试实现一种算法，以在没有 Gale-Shapley 算法的情况下使用蛮力方法找到所有稳定的婚姻解决方案（因为它只给了我们其中的 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'}
优化答案
（受 启发，但不需要 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 是：
[
[('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')]
]
警告：输出的大小是阶乘 (n)，其中 n 是较小输入的大小。在 n = 14 时，这需要 100 GB 的内存来存储，比大多数现代系统都多。
旧答案
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))]
有效配对是：
[
(('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'))
]
这是一种蛮力方法（不要将其用于长列表），只需对总体进行足够多的抽样以确保您拥有所有可能的组合，制作一组组合并对结果进行排序。
from random import sample
x = ["a","b","c"]
y = ['d','e','f']
z = {tuple(sample(y,3)) for i in range(25)}
result = sorted([list(zip(x,z_)) for z_ in z])
>>>result
[[('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')]]
这不是要走的路，它只是一种不同的方法。
将 "wives" 与 "husbands" 的所有排列组合，您将获得所有组合。
import itertools
import numpy as np
husbands = ['d', 'e', 'f']
wifes = ['a', 'b', 'c']
permutations = list(itertools.permutations(husbands))
repetition = [wifes for _ in permutations]
res = np.dstack((repetition,permutations))
print(res)
结果是：
[[['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']]]
如果您更喜欢元组：
res = res.view(dtype=np.dtype([('x', np.dtype('U1')), ('y', np.dtype('U1'))]))
res = res.reshape(res.shape[:-1])
print(res)
结果：
[[('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')]]
我正在尝试实现一种算法，以在没有 Gale-Shapley 算法的情况下使用蛮力方法找到所有稳定的婚姻解决方案（因为它只给了我们其中的 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'}
优化答案
（受
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 是：
[
[('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')]
]
警告：输出的大小是阶乘 (n)，其中 n 是较小输入的大小。在 n = 14 时，这需要 100 GB 的内存来存储，比大多数现代系统都多。
旧答案
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))]
有效配对是：
[
(('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'))
]
这是一种蛮力方法（不要将其用于长列表），只需对总体进行足够多的抽样以确保您拥有所有可能的组合，制作一组组合并对结果进行排序。
from random import sample
x = ["a","b","c"]
y = ['d','e','f']
z = {tuple(sample(y,3)) for i in range(25)}
result = sorted([list(zip(x,z_)) for z_ in z])
>>>result
[[('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')]]
这不是要走的路，它只是一种不同的方法。
将 "wives" 与 "husbands" 的所有排列组合，您将获得所有组合。
import itertools
import numpy as np
husbands = ['d', 'e', 'f']
wifes = ['a', 'b', 'c']
permutations = list(itertools.permutations(husbands))
repetition = [wifes for _ in permutations]
res = np.dstack((repetition,permutations))
print(res)
结果是：
[[['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']]]
如果您更喜欢元组：
res = res.view(dtype=np.dtype([('x', np.dtype('U1')), ('y', np.dtype('U1'))]))
res = res.reshape(res.shape[:-1])
print(res)
结果：
[[('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')]]