網易游戲筆試題算法題之一，可以用C++,Java,Python，由于Python代碼量較小，于是我選擇Python語言。
算法總體思路是從1，2，3……N這個排列開始，一直計算下一個排列，直到輸出N,N-1,……1為止
那么如何計算給定排列的下一個排列？
考慮[2，3，5，4，1]這個序列，從后往前尋找第一對遞增的相鄰數字，即3，5。那么3就是替換數，3所在的位置是替換點。
將3和替換點后面比3大的最小數交換，這里是4，得到[2,4,5,3,1]。然后再交換替換點后面的第一個數和最后一個數，即交換5，1。就得到下一個序列[2，4，1，3，5]
代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
def arrange(pos_int): #將1-N放入列表tempList中，已方便處理 tempList = [i+1 for i in range(pos_int)] print(tempList) while tempList != [pos_int-i for i in range(pos_int)]: for i in range(pos_int-1,-1,-1): if(tempList[i]>tempList[i-1]): #考慮tempList[i-1]后面比它大的元素中最小的，交換。 minmax = min([k for k in tempList[i::] if k > tempList[i-1]]) #得到minmax在tempList中的位置 index = tempList.index(minmax) #交換 temp = tempList[i-1] tempList[i-1] = tempList[index] tempList[index] = temp #再交換tempList[i]和最后一個元素，得到tempList的下一個排列 temp = tempList[i] tempList[i] = tempList[pos_int-1] tempList[pos_int-1] = temp print(tempList) break arrange(5) |
以上這篇非遞歸的輸出1-N的全排列實例(推薦)就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
