Detaillierte Erläuterung der Methode zur nichtrekursiven Ausgabe der vollständigen Permutation von 1-N

Der folgende Editor zeigt Ihnen ein nicht rekursives vollständiges Permutationsbeispiel für die Ausgabe von 1-N (empfohlen). Der Herausgeber findet es ziemlich gut, deshalb werde ich es jetzt mit Ihnen teilen und es allen als Referenz geben. Folgen wir dem Editor und werfen wir einen Blick darauf.

Eine der Algorithmusfragen im NetEase-Spieltest kann in C++, Java oder Python geschrieben werden. Da die Menge an Python-Code gering ist, habe ich mich für Python entschieden Sprache.

Die allgemeine Idee des Algorithmus besteht darin, mit der Anordnung von 1, 2, 3 ... N zu beginnen und die nächste Anordnung so lange zu berechnen, bis N, N-1, ... 1 ausgegeben wird

Wie berechnet man also die nächste Permutation für eine bestimmte Permutation?

Betrachten Sie die Folge [2, 3, 5, 4, 1] und suchen Sie nach dem ersten Paar aufsteigender benachbarter Zahlen von hinten nach vorne, also 3, 5. Dann ist 3 die Ersetzungsnummer und die Position von 3 ist der Ersetzungspunkt.

Ersetzen Sie 3 mit der kleinsten Zahl nach dem Ersetzungspunkt, die größer als 3 ist, hier ist es 4, um [2,4,5,3,1] zu erhalten. Tauschen Sie dann die erste Zahl und die letzte Zahl nach dem Ersetzungspunkt aus, also 5,1. Sie erhalten die nächste Sequenz [2, 4, 1, 3, 5]

Der Code lautet wie folgt:

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)

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Methode zur nichtrekursiven Ausgabe der vollständigen Permutation von 1-N. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!