1-Nの全順列を非再帰的に出力する方法の詳細説明

以下のエディターは、1-N を出力する非再帰的な完全な置換の例を提供します (推奨)。編集者はこれがとても良いものだと思ったので、皆さんの参考として今から共有します。エディターをフォローして見てみましょう

NetEase ゲームの筆記テストのアルゴリズムの質問の 1 つは、C++、Java、または Python で記述できます。Python コードの量が少ないため、Python 言語を選択しました。

アルゴリズムの一般的な考え方は、1、2、3...Nの配置から開始し、N、N-1、...1を出力するまで次の配置を計算し続けることです

では、与えられた配列の次の順列を計算するにはどうすればよいでしょうか?

シーケンス [2、3、5、4、1] を考え、後ろから前に増加する隣接する数字の最初のペア、つまり 3、5 を探します。次に、3 が置換番号で、3 の位置が置換ポイントになります。

3 を、置換点の後の 3 より大きい最小の数字 (ここでは 4) に交換し、[2,4,5,3,1] を取得します。次に、置換点の後の最初の番号と最後の番号、つまり 5,1 を交換します。次のシーケンス [2, 4, 1, 3, 5] を取得します

コードは次のとおりです:

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)

以上が1-Nの全順列を非再帰的に出力する方法の詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。