与えられた文字列の次に大きい順列を求めるアルゴリズム

質問

与えられた文字列の次に大きい順列を見つけるための効率的なアルゴリズムが欲しい。

どのように解決するのですか？

ウィキペディアには 記事 があります。また、次の順列を生成するアルゴリズムも記述されています。

引用元

次のアルゴリズムは、与えられた並べ換えの後に辞書式に次の並べ換えを生成します。これは与えられた並べ換えをインプレースで変更します。

1. 最も高いインデックスを探す i となるような s[i] < s[i+1] . そのようなインデックスが存在しない場合、順列は最後の順列となる。
2. 最も高いインデックスを見つける j > i となるような s[j] > s[i] . このような j は存在しなければなりません。 i+1 はそのようなインデックスであるため、存在する必要があります。
3. スワップ s[i] と s[j] .
4. index以降の全ての要素の順序を逆転させる。 i を経て最後の要素まで。