python - 暴力稳定婚姻，如何实现2个列表之间所有可能的配对？

Question

我正在尝试实现一种算法，通过暴力方法找到所有稳定的婚姻解决方案，而无需使用 Gale-Shapley 算法(因为它只提供了其中的 2 个)。我正在使用 rosettacoode 中找到的检查机制但我很难找到一种方法来创建所有可能的匹配而不重复(就像 2 个 for 循环那样)例如

 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'}

Answer 1

优化答案

(受 @Jonas 启发，但不需要 Numpy):

from itertools import permutations
l1 = ["a", "b", "c"]
l2 = ["d", "e", "f"]
valid_pairings = [sorted(zip(i, l2)) for i in permutations(l1)]

有效配对是:

[
 [('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'))
]