非递归的输出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]
代码如下：
defarrange(pos_int): #将1-N放入列表tempList中，已方便处理 tempList=[i+1foriinrange(pos_int)] print(tempList) whiletempList!=[pos_int-iforiinrange(pos_int)]: foriinrange(pos_int-1,-1,-1): if(tempList[i]>tempList[i-1]): #考虑tempList[i-1]后面比它大的元素中最小的，交换。 minmax=min([kforkintempList[i::]ifk>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的全排列实例(推荐)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。