2

我正在尝试实现一种算法，以在没有 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)]

UPDATE1： 到目前为止，所有解决方案都无法在它变大时运行它。我可能应该递归地做它而不存储长数据结构，当我得到它时测试单个结果并丢弃其他结果。我提出了这个解决方案，但仍然有问题，因为给了我一些重复和缺少的东西。我不知道如何解决它，对不起，我的大脑正在融化！

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

3 回答 3

3

优化答案

（受@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'))
]
于 2018-12-13T15:53:16.603 回答
1

这是一种蛮力方法（不要将其用于长列表），只需对总体进行足够多次的抽样以确保您拥有所有可能的组合，然后对其进行一组排序并对结果进行排序。

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

这不是要走的路，这只是一种不同的方法。

于 2018-12-13T16:04:44.103 回答
1

将“妻子”与“丈夫”的所有排列组合起来，就得到了所有组合。

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')]]
于 2018-12-13T16:33:07.417 回答