非遞歸的輸出1-N的全排列實(shí)例(推薦)
更新時(shí)間：2017年04月11日 08:47:18 投稿：jingxian
下面小編就為大家?guī)?lái)一篇非遞歸的輸出1-N的全排列實(shí)例(推薦)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
網(wǎng)易游戲筆試題算法題之一，可以用C++,Java,Python，由于Python代碼量較小，于是我選擇Python語(yǔ)言。
算法總體思路是從1，2，3……N這個(gè)排列開(kāi)始，一直計(jì)算下一個(gè)排列，直到輸出N,N-1,……1為止
那么如何計(jì)算給定排列的下一個(gè)排列？
考慮[2，3，5，4，1]這個(gè)序列，從后往前尋找第一對(duì)遞增的相鄰數(shù)字，即3，5。那么3就是替換數(shù)，3所在的位置是替換點(diǎn)。
將3和替換點(diǎn)后面比3大的最小數(shù)交換，這里是4，得到[2,4,5,3,1]。然后再交換替換點(diǎn)后面的第一個(gè)數(shù)和最后一個(gè)數(shù)，即交換5，1。就得到下一個(gè)序列[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]和最后一個(gè)元素，得到tempList的下一個(gè)排列
temp = tempList[i]
tempList[i] = tempList[pos_int-1]
tempList[pos_int-1] = temp
print(tempList)
break
arrange(5)
以上這篇非遞歸的輸出1-N的全排列實(shí)例(推薦)就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
Python實(shí)現(xiàn)的Excel文件讀寫(xiě)類
這篇文章主要介紹了Python實(shí)現(xiàn)的Excel文件讀寫(xiě)類,涉及Python針對(duì)Excel常見(jiàn)的讀寫(xiě)、打印等操作技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-07-07
Python實(shí)現(xiàn)將實(shí)體類列表數(shù)據(jù)導(dǎo)出到Excel文件
在數(shù)據(jù)處理和報(bào)告生成中,將實(shí)體類的列表數(shù)據(jù)導(dǎo)出到Excel文件是一項(xiàng)常見(jiàn)任務(wù),Python提供了多種庫(kù)來(lái)實(shí)現(xiàn)這一目標(biāo),下面就來(lái)跟隨小編一起學(xué)習(xí)一下吧2025-01-01
把MySQL表結(jié)構(gòu)映射為Python中的對(duì)象的教程
這篇文章主要介紹了簡(jiǎn)單地把MySQL表結(jié)構(gòu)映射為Python中的對(duì)象的方法,用到了Python中的SQLAlchemy庫(kù),需要的朋友可以參考下2015-04-04
在本篇內(nèi)容里小編給大家整理的是一篇關(guān)于django有哪些好處和優(yōu)點(diǎn)的相關(guān)內(nèi)容，有需要的朋友們可以參考下。2020-09-09
這篇文章主要介紹了詳解pandas獲取Dataframe元素值的幾種方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06
itchat是一個(gè)開(kāi)源的微信個(gè)人號(hào)接口，使用python調(diào)用微信從未如此簡(jiǎn)單。這篇文章主要介紹了Python微信操控itchat的方法,需要的朋友可以參考下2019-05-05
解決Tensorflow sess.run導(dǎo)致的內(nèi)存溢出問(wèn)題
今天小編就為大家分享一篇解決Tensorflow sess.run導(dǎo)致的內(nèi)存溢出問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-02-02
關(guān)于python基礎(chǔ)數(shù)據(jù)類型bytes進(jìn)制轉(zhuǎn)換
Python 3.x之后，Python自帶字符默認(rèn)使用utf-8格式編碼和顯示,bytes數(shù)據(jù)類型是utf-8格式的二進(jìn)制形式的不可變序列,需要的朋友可以參考下2023-05-05
tensorflow:指定gpu 限制使用量百分比,設(shè)置最小使用量的實(shí)現(xiàn)
今天小編就為大家分享一篇tensorflow:指定gpu 限制使用量百分比,設(shè)置最小使用量的實(shí)現(xiàn)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-02-02
這篇文章主要介紹了Python中的lstrip()方法使用簡(jiǎn)介,是Python入門(mén)的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-05-05