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)]

  while tempList != [pos_int-i for i in range(pos_int)]:
    for i in range(pos_int-1,-1,-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


Related articles: