自然数/整数 - 関数 - 最小自由数 (最小除外数)

定義

（ \(0\) を含む）自然数の部分集合 \(T\) について 次の関数を mex (minimum excludant) という.

\[\mathrm{mex}~(T) := \min (\mathbb N \setminus T).\]

例えば

• \(\mathrm{mex}(\{\}) = 0\)
• \(\mathrm{mex}(\{0,1,2\}) = 3\)
• \(\mathrm{mex}(\{0,2\}) = 1\)

実装

\(T\) が有限集合で \(N = |T|\) とすると \(\mathrm{mex}(T) \leq N\) なので, \(N\) 以下の数を列挙することで \(O(N)\) で求められる.

/// Natural Numbers - Minimal Exclusion number, mex
pub fn mex(xs: &Vec<usize>) -> usize {
    let m = xs.len();
    let mut memo = vec![false; m + 1];
    for &x in xs.iter().filter(|&x| x <= &m) {
        memo[x] = true;
    }
    memo.iter().take_while(|&&b| b).count()
}

#[cfg(test)]
mod test_binom_modint {
    use crate::num::mex::*;

    #[test]
    fn it_works() {
        assert_eq!(mex(&vec![1, 2, 3]), 0);
        assert_eq!(mex(&vec![0, 2, 3]), 1);
        assert_eq!(mex(&vec![0, 1, 3]), 2);
        assert_eq!(mex(&vec![0, 1000]), 1);
    }
}