非遞歸輸出1-N的全排列的方法詳解

下面小編就為大家帶來一篇非遞歸的輸出1-N的全排列實例(推薦)。小編覺得蠻不錯的，現在就分享給大家，也給大家做個參考。一起跟著小編過來看看吧

網易遊戲筆試題演算法題之一，可以用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]

程式碼如下：

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的全排列的方法詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！