Non recursive output 1 N full permutation instance of recommended
- 2020-05-30 20:25:31
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)