次の順列

中級

Next Permutation

次の順列(Next Permutation)は、与えられた数列を辞書順で次に来る順列にインプレースで並べ替えるアルゴリズムです。右から最初の減少地点(pivot)を見つけて交換し、後ろの部分を反転してO(n)で求めます。

実装順列インプレースO(n)

次の順列は、ある数列が与えられたとき、同じ要素で作れるすべての順列を辞書順に並べたときに「すぐ次」に来る順列を見つけるアルゴリズムです。追加配列なしでインプレースにO(n)で変換します。

1/14

数列 [1, 3, 5, 4, 2] の辞書順で次の順列をインプレースで求めましょう。右から「減少が途切れる地点」を見つけることから始めます。

中級

Next Permutation

実装順列インプレースO(n)

1/14

数列 [1, 3, 5, 4, 2] の辞書順で次の順列をインプレースで求めましょう。右から「減少が途切れる地点」を見つけることから始めます。