概要

長さ $N$ の数列 $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 が便利

内部実装

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
}

出典: next_permutation と同様に列挙できるもの一覧 - ブログ名

変更のある最も前側の場所は、後ろ側から見て初めて単調減少ではなくなる場所である

例:

5 2 1 4 3 0 の場合:
後ろから見て 4 3 0 までは単調減少している。
5 2 1 から始まるものの中で 4 3 0 で終わるのは最大のもの。
つまり、5 2 1 の部分を次に進める。4 3 0 の部分の中から 1 の次の数として 3 を選ぶ
次の上3桁は 5 2 3 となり、下3桁 は 4 1 0 をソートした 0 1 4 となる。
したがって以下のようになる
5 2 3 0 1 4

計算量