Explication détaillée de la méthode de sortie non récursive de la permutation complète de 1-N

L'éditeur suivant vous proposera un exemple de permutation complète non récursive de sortie 1-N (recommandé). L'éditeur le trouve plutôt bon, je vais donc le partager avec vous maintenant et le donner comme référence pour tout le monde. Suivons l'éditeur et jetons un coup d'œil.

L'une des questions d'algorithme du test écrit du jeu NetEase peut être écrite en C++, Java ou Python. La quantité de code Python étant faible, j'ai choisi Python. langue.

L'idée générale de l'algorithme est de partir de l'arrangement de 1, 2, 3...N, et de continuer à calculer l'arrangement suivant jusqu'à ce que N, N-1,...1 soit sortie

Alors comment calculer la prochaine permutation pour une permutation donnée ?

Considérez la séquence [2, 3, 5, 4, 1] et recherchez la première paire de nombres adjacents croissants d'arrière en avant, c'est-à-dire 3, 5. Alors 3 est le numéro de remplacement et la position 3 est le point de remplacement.

Échangez 3 avec le plus petit nombre après le point de remplacement qui est supérieur à 3, ici c'est 4, pour obtenir [2,4,5,3,1]. Échangez ensuite le premier numéro et le dernier numéro après le point de remplacement, c'est-à-dire échangez 5,1. Vous obtiendrez la séquence suivante [2, 4, 1, 3, 5]

Le code est le suivant :

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)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!