概要

長さ $N$ の数列 $A$ が与えられる。辞書順で $A$ より大きな最小の置換 $A$ があればそれを求め、なければ報告をする。

Rust の next_permutation

permutohedron というクレートにある

• fn next_permutation(&mut self) -> bool
  • 次の permutation がなければ false を返す。
• 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!)$ である。

[証明]