算法需求如下：

有八个人对应分配了八个位置，但是其中一些人对自己的位置并不满意，问在最多人满意的情况下，最后调换位置的有哪几个？人物对应喜好如下图：

图例：（A和B都喜欢C位，但是分配到的分别是A位和B位）

image.png

思路：

如果拿到问题，我们首先对于问题做一个分析：对于要求满意的人尽可能多，也就是调换位置的人尽可能多，求调换位置的有多少，那我们可以换个思路，不调换位置的有多少，假如说它本身就在自己喜欢的位置，那么他不用调换位置，如果两个人刚好喜欢对方喜欢的位置，那么可以互换，剩下的如果还有人喜欢那个位置，那么这个人就要被淘汰，比如上图的A和B和C，A和B都喜欢C位而C喜欢A位，那么如果把A淘汰，那么C的位置就得不到满足（A被淘汰意味着A就坐在A位），那么如果淘汰B，看起来是个正确的选择，因为C可以和A互换，得到都满意的结果。

image.png

知道了需要 剔除那些元素，下面开始实现这个算法。

先用一个列表表示人物的位置关系

U = 【2,2,0,5,3,5,7,4】

前两个元素都想在第二个位置

U【1】=U【2】=1

首先，通过观察我们发现，对于一般的位置而言，我们有两个输入的都会删除其中一个，比如A和B，那么先贴代码：

遇到问题没人解答？小编创建了一个Python学习交流QQ群：895817687 寻找有志同道合的小伙伴，
互帮互助,群里还有不错的视频学习教程和PDF电子书！

def max_perm(m):
 n = len(m)
 A = set(range(n))
 count = [0]*n
 for i in m:
 count[i]+=1
 Q = [i for i in A if count[i] == 0]
 print(Q)
 while Q:
 i = Q.pop()
 print(i)
 A.remove(i)
 j = m[i]
 count[j] -= 1
 if count[j] == 0:
 Q.append(j)
 return A
m = [2,2,0,5,3,5,7,4]
print(max_perm(m))

创建一个长度为8的列表，记录位置，然后一个全部为0的列表用来记录对应的输入，比如第三个位置有两个输入就记为2，那么我们得到一个记录入边数目的列表为[1,0,2,1,1,2,0,1]

也就是代码中的count（计数器）

Q是为了记录count中为0的元素对应的在A中的元素，也就是没有入边的位置，没人喜欢的位置，直接删除，也就是{1,6}，从图中可以看出，第2个位置和第7个位置没人想坐（没有边输入）故直接淘汰

接着进入while循环，将栈中顶部元素弹出，也就是6，将6对应的A中的元素也删除，因为这个人和这个位置是绑定的，位置没了，人也就被淘汰了，他只能坐6号了。

接着获取M列表中对应的第i个元素获取对应元素，如果这个元素入边数目为1，那么这个就是下一个要删除的对象，因为没了i ，就一个入边也没了，以此推下去，我在代码中顺便打印了对应弹栈出来的元素，方便学习。

image.png

[1, 6]
6
7
4
3
1
最后结果：{0, 2, 5}