算法需求如下：

有八個人對應分配了八個位置，但是其中一些人對自己的位置并不滿意，問在最多人滿意的情況下，最后調(diào)換位置的有哪幾個？人物對應喜好如下圖：

圖例：（A和B都喜歡C位，但是分配到的分別是A位和B位）

思路：

如果拿到問題，我們首先對于問題做一個分析：對于要求滿意的人盡可能多，也就是調(diào)換位置的人盡可能多，求調(diào)換位置的有多少，那我們可以換個思路，不調(diào)換位置的有多少，假如說它本身就在自己喜歡的位置，那么他不用調(diào)換位置，如果兩個人剛好喜歡對方喜歡的位置，那么可以互換，剩下的如果還有人喜歡那個位置，那么這個人就要被淘汰，比如上圖的A和B和C，A和B都喜歡C位而C喜歡A位，那么如果把A淘汰，那么C的位置就得不到滿足（A被淘汰意味著A就坐在A位），那么如果淘汰B，看起來是個正確的選擇，因為C可以和A互換，得到都滿意的結果。

知道了需要 剔除那些元素，下面開始實現(xiàn)這個算法。

先用一個列表表示人物的位置關系

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

前兩個元素都想在第二個位置

U【1】=U【2】=1

首先，通過觀察我們發(fā)現(xiàn)，對于一般的位置而言，我們有兩個輸入的都會刪除其中一個，比如A和B，那么先貼代碼：

遇到問題沒人解答？小編創(chuàng)建了一個Python學習交流QQ群：895817687 尋找有志同道合的小伙伴， 互幫互助,群里還有不錯的視頻學習教程和PDF電子書！def max_perm(m):n = len(m)A = set(range(n))count = [0]*nfor i in m:count[i]+=1Q = [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] -= 1if count[j] == 0:Q.append(j)return A m = [2,2,0,5,3,5,7,4] print(max_perm(m))

創(chuàng)建一個長度為8的列表，記錄位置，然后一個全部為0的列表用來記錄對應的輸入，比如第三個位置有兩個輸入就記為2，那么我們得到一個記錄入邊數(shù)目的列表為[1,0,2,1,1,2,0,1]

也就是代碼中的count（計數(shù)器）

Q是為了記錄count中為0的元素對應的在A中的元素，也就是沒有入邊的位置，沒人喜歡的位置，直接刪除，也就是{1,6}，從圖中可以看出，第2個位置和第7個位置沒人想坐（沒有邊輸入）故直接淘汰

接著進入while循環(huán)，將棧中頂部元素彈出，也就是6，將6對應的A中的元素也刪除，因為這個人和這個位置是綁定的，位置沒了，人也就被淘汰了，他只能坐6號了。

接著獲取M列表中對應的第i個元素獲取對應元素，如果這個元素入邊數(shù)目為1，那么這個就是下一個要刪除的對象，因為沒了i ，就一個入邊也沒了，以此推下去，我在代碼中順便打印了對應彈棧出來的元素，方便學習。

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

總結

以上是生活随笔為你收集整理的最大排列问题的算法实现（Python）究竟最后调换位置的有哪几个？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。