長さ $N$ の数列 $A$ が与えられる。辞書順で $A$ より大きな最小の置換 $A$ があればそれを求め、なければ報告をする。
permutohedron というクレートにある
fn next_permutation(&mut self) -> bool
fn prev_permutation(&mut self) -> bool
参考: permutohedron::LexicalPermutation - Rust
ただ、順列全列挙したいだけであれば、Itertools の permutations を使えば良い。
辞書順で次の要素を取得したいみたいなケースで next_permutation が便利
next_permutation
と同様に列挙できるもの一覧 - ブログ名
pub fn next_permutation<T: Ord>(a: &mut [T]) -> bool {
let Some(i) = a.windows(2).rposition(|w| w[0] < w[1]) else { return false };
let j = a.iter().rposition(|x| x > &a[i]).unwrap();
a.swap(i, j);
a[i + 1..].reverse();
true
}
値の重複がない長さ $N$ の配列をソートした後、$N!$ 回 next_permutation を呼び出したときの計算量は $O(N!)$ である。
[証明]