Detailed explanation of the method of non-recursively outputting the full permutation of 1-N

The following editor will bring you a non-recursive output 1-N full permutation example (recommended). The editor thinks it’s pretty good, so I’ll share it with you now and give it as a reference. Let’s follow the editor and take a look.

One of the algorithm questions in the NetEase game written test can be written in C++, Java, or Python. Since the amount of Python code is small, I chose the Python language.

The general idea of ​​the algorithm is to start from the arrangement of 1, 2, 3...N, and keep calculating the next arrangement until the output is N, N-1,...1

So how to calculate the next permutation for a given permutation?

Consider the sequence [2, 3, 5, 4, 1] and look for the first pair of increasing adjacent numbers from back to front, that is, 3, 5. Then 3 is the replacement number, and the position of 3 is the replacement point.

Exchange 3 with the smallest number after the replacement point that is greater than 3, here it is 4, and get [2,4,5,3,1]. Then exchange the first number and the last number after the replacement point, that is, exchange 5,1. You will get the next sequence [2, 4, 1, 3, 5]

The code is as follows:

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)

The above is the detailed content of Detailed explanation of the method of non-recursively outputting the full permutation of 1-N. For more information, please follow other related articles on the PHP Chinese website!