def GS_matching(MP, WP):
    # MP是男士的择偶排序的集合 WP是女士的
    m = len(MP)
    n = len(WP)
    # 给出男士和女士是否单身的数组用以评价
    isManFree = [True] * m
    isWomenFree = [True] * n
    # 男士是否向女士求过婚的表格
    isManProposed = [[False for i in range(n)] for j in range(m)]
    # 最后匹配得出的组合 返回结果
    match = [(-1, -1)] * m

    while (True in isManFree):
        # 找到第一个单身男士的索引值
        indexM = isManFree.index(True)
        # 对每个女生求婚  找到男士优先列表中还没找到对象的女士
        if (False in isManProposed[indexM]):
            indexW = -1  # 找到还没被求婚的排名靠前的女士的索引
            for i in range(len(MP[indexM])):
                w = MP[indexM][i]
                if (not isManProposed[indexM][w]):
                    indexW = w
                    break
            isManProposed[indexM][indexW] = True
            if (isWomenFree[indexW]):  # 女士单身且她愿意接受这个男士
                isWomenAccept = False
                for i in range(len(WP[indexW])):
                    if (WP[indexW][i] == indexM):
                        isWomenAccept = True
                if (isWomenAccept):
                    isWomenFree[indexW] = False
                    isManFree[indexM] = False
                    match[indexM] = (indexM, indexW)
            else:
                indexM1 = -1  # 与当前女士已匹配的男士的索引
                isWomenAccept = False
                for i in range(len(WP[indexW])):  # 找到这个人是否能被这个女士接受
                    if (WP[indexW][i] == indexM):
                        isWomenAccept = True
                if (isWomenAccept):
                    for j in range(m):
                        if (match[j][1] == indexW):
                            indexM1 = j
                            break
                    if (WP[indexW].index(indexM) < WP[indexW].index(indexM1)):
                        isManFree[indexM1] = True
                        isManFree[indexM] = False
                        match[indexM] = (indexM, indexW)
    # 删除没有进行配对的值  即任一方值为-1
    for i in range(len(match) - 1, -1, -1):
        # 倒序循环，从最后一个元素循环到第一个元素。不能用正序循环，因为正序循环删除元素后后续的列表的长度和元素下标同时也跟着变了，len(list)是动态的。
        if (match[i][0] == -1 or match[i][1] == -1):
            match.pop(i)

    return match


if __name__ == "__main__":
    print("*************测试*******************")
    MP = [[0, 1], [0, 1, 2], [0, 1, 2, 3]]
    WP = [[1, 0, 2], [2, 1, 0], [2, 1, 0], [ 2, 1, 0],]

    SM = GS_matching(MP, WP)
    print(1,SM)
    mapping = {key: value for key, value in SM}
    print(mapping.get(0))
    if mapping.get(0) == None:
        print(1)