Python 实现匈牙利算法

def hungary(edges):
    result = set()
    lenA = max(edge[0] for edge in edges) + 1
    lenB = max(edge[1] for edge in edges) + 1

    def allVectorsGen():
        for x in xrange(lenA):
            yield x, None
        for x in xrange(lenB):
            yield None, x

    usedVectors = set()

    def getPath(inResult, startVector, path=()), pathUsedVectors=None):
        pathUsedVectors = pathUsedVectors or set()
        # No need to enumerate edge already in path.
        for edge in edges - set(path):
            if (edge in result) != inResult:
                continue
            vectors = set(((edge[0], None), (None, edge[1])))
            if not startVector in vectors:
                continue
            vectors.remove(startVector)
            endVector = vectors.pop()
            if endVector in pathUsedVectors:
                continue
            pathUsedVectors.add(endVector)
            path = path + (edge,)
            # Invert inResult, know & don't know of a & b
            subPath = getPath(not inResult, endVector, path, pathUsedVectors)
            if not subPath is None:
                return subPath
            elif len(path) % 2 == 1 and not endVector in usedVectors:
                return path
        return None

    while len(result) < min(lenA, lenB):
        for vector in allVectorsGen():
            if vector in usedVectors:
                continue
            path = getPath(False, vector)
            if not path is None:
                result ^= set(path)
                # Every path found, both start vector & end vector will be
                # removed from free vectors.
                usedVectors.add(vector)  # Start vector
                usedVectors.add(((path[-1][0] if vector[0] is None else None),
                                 (path[-1][1] if vector[1] is None else None)))
                # End vector
                break
        else:
            break

    return result

if __name__ == '__main__':
    print hungary(set([(0, 1), (0, 4),
                       (1, 1), (1, 2), (1, 3),
                       (2, 0), (2, 4),
                       (3, 0), (3, 1), (3, 4),
                       (4, 1)]))

坑：

1. 生成器表达式生成的生成器只能调用一次。
2. set构造器不支持*arg的构造方式。
3. 直到Python 2.7.3，还没有frozendict，可以使用frozenset代替。后来我没用。所以dict不能哈希，也就是不能直接入set，可以用frozenset(dictA.iteritems())代替。
4. dict转序列的时候只保留键,序列转dict必须每个项的长度为2，所以强转这事儿在dict和序列之间不可逆。
5. **传参数必须是dict，不提供自动转换成dict的功能。
6. 默认参数传可变对象的时候会造成静态问题，简单的解决方案是传p=None然后p = p || set()
7. 在没有歧义的情况下可以使用()来声明一个空元组，真萌。