Home >Backend Development >Python Tutorial >Detailed explanation of the method of non-recursively outputting the full permutation of 1-N

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

Y2J
Y2JOriginal
2017-04-26 11:18:511999browse

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!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn