[伯俊/python 3]10972次の順番

https://www.acmicpc.net/problem/10972

に答える

n個の長さのシーケンスが与えられると、次のシーケンスが出力され、最後のシーケンスであれば−1が出力される.最初は制限は見られず、Pythonに内蔵された配列ですべてのシーケンスを作成し、正しいインデックスを出力します.ただし、このような場合、1<=N<=10000、O(N^2)のためにメモリオーバーフロー、タイムアウトなどの問題が発生する可能性があります.そこで,今回の問題ではNext Permutationアルゴリズムを用いる.
Next PermutationアルゴリズムはstlにC++で埋め込まれているが,Pythonではそうではないため,直接実現する必要がある.この機会にしっかり整理しておきましょう.
問題例1のN=4のシーケンスを作成します.
このとき、第1シーケンスは1 2 3 4であり、以下のようになる.

1 2 3 4 -> 1 2 4 3 -> 1 3 2 4 -> ... -> 4 3 2 1

1 2 3 4->1 2 4 3プロセス

一番後ろから探索し、前の数字が後ろの数字より小さい場合を探します.以上の状況は(3, 4)で見つけることができます.このとき、3より大きい値が現れるかどうかを最後尾から探せば、4が現れる.両者を交換すると1 2 4 3となる.

1 2 4 3->1 3 2 4プロセス

同じ方法で前の数字が後の数字より小さくなった場合を探します.以上の状況は(2, 4)で見つけることができます.このとき、2より大きい値が現れるかどうかは、一番後ろから探します.これは3です.このとき、この2つの値が交換され、結果は1 3 4 2であった.変更後の3を基準として1 34 2に分け、前の値1 3と後の値を並べ替えた結果、2 4となった.結果は1 3 2 4になります.
したがって,以下にシーケンスを求めるアルゴリズムを以下に示す.
一番後ろから

数列を探索し、前の数字が後ろの数字より小さいかどうかを探索する.

が小さくなる場合は、数字に準じる.その後、一番後ろから探索し、基準より大きい数字があるかどうかを確認します.

より大きな数字

があれば、標準数字と大きな数字を交換します.

を基準とした数字を前後に分け、前の数列と後の数列を並べ替えた後、これらの数列を加算します.

結果として、与えられたシーケンスの次のシーケンスを求めることができる.

コード#コード#

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

for i in range(N-1, 0, -1):
    if arr[i-1] < arr[i]:   # 앞 열의 값이 바로 뒷 열의 값보다 작으면
        for j in range(N-1, 0, -1): # 그 앞 열의 값을 맨 뒷 열부터 비교
            if arr[i-1] < arr[j]:   # 그 앞 열의 값이 뒤에 있는 열보다 작을경우
                arr[i-1], arr[j] = arr[j], arr[i-1] # 그 두 값을 스왑
                arr = arr[:i] + sorted(arr[i:])
                print(*arr)
                exit()

print(-1)

リファレンス

以下は参考にしたホームページです.ありがとうございます.
https://ji-gwang.tistory.com/262
https://velog.io/@tomato2532/NextPermutation