# Non recursive output 1 N full permutation instance of recommended

• 2020-05-30 20:25:31
• OfStack

Netease game pen test question algorithm 1, can use C + +, Java, Python, because Python code amount is small, so I choose Python language.

The general idea of the algorithm is 1,2,3... The N permutation starts, and 1 calculates the next permutation until the output is N, N-1... 1 so far

So how do you compute the next permutation for a given permutation?

Consider the sequence [2,3,5,4,1] and look backwards for the first pair of incrementing adjacent digits, namely 3,5. So 3 is the number of substitutions, and 3 is the substitution point.

You swap 3 with the smallest number greater than 3 after the substitution point, which is 4, and you get [2,4,5,3,1]. And then you swap the first number after the substitution point with the last number, which is 5,1. You get the next sequence [2,4,1,3,5]

The code is as follows:

``````
def arrange(pos_int):
# will 1-N In the list tempList In, has been handled conveniently
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]):
# consider tempList[i-1] The smallest of the next elements that are bigger than that.
minmax = min([k for k in tempList[i::] if k > tempList[i-1]])
# get minmax in tempList The position of
index = tempList.index(minmax)
# exchange
temp = tempList[i-1]
tempList[i-1] = tempList[index]
tempList[index] = temp

# To exchange tempList[i] And the last 1 I have 1, 1, 1, 1, 1, 1 tempList Under the 1 A permutation
temp = tempList[i]
tempList[i] = tempList[pos_int-1]
tempList[pos_int-1] = temp

print(tempList)
break

arrange(5)

``````

Related articles: