非递归输出1-N的全排列的方法详解

来源：动视网责编：小OO 时间：2020-11-27 14:24:36

非递归输出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]。代码如下：

推荐度：

点击下载本文 文档为doc格式

导读网易游戏笔试题算法题之一，可以用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-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的全排列的方法详解

推荐度：

点击下载本文 文档为doc格式

标签：非递归全排列递归，输出全排列，python

热门焦点

非递归输出1-N的全排列的方法详解

非递归输出1-N的全排列的方法详解

非递归输出1-N的全排列的方法详解

最新推荐

猜你喜欢

热门推荐