組み合わせ \({}_nC{}_m\)

For each \(\{ x_i : 0 \leq i \lt m, 0 \leq x_i \lt n, x_i \gt x_j \}\)

// C[n;m]
struct Combination { n: usize, m: usize, ar: Vec<usize> }
impl Combination {
    fn new(n: usize, m: usize) -> Combination {
        let mut ar = vec![0; m];
        for i in 0..m { ar[i] = m - i - 1 }
        Combination { n: n, m: m, ar: ar }
    }
}
impl Iterator for Combination {
    type Item = Vec<usize>;
    fn next(&mut self) -> Option<Vec<usize>> {
        if self.m == 0 {
            if self.n == 0 {
                return None
            } else {
                self.n = 0;
                return Some(vec![]);
            }
        }
        if self.ar[self.m-1] > self.n - self.m { return None }
        let r = self.ar.clone();
        self.ar[0] += 1;
        let mut c = 0;
        for i in 0..self.m-1 {
            if self.ar[i] >= self.n - i {
                self.ar[i + 1] += 1;
                c = i + 1;
            } else {
                break;
            }
        }
        for i in (0..c).rev() {
            self.ar[i] = self.ar[i+1] + 1;
        }
        return Some(r);
    }
}

Example

fn main() {
    let mut count = 0;
    for a in Combination::new(6, 3) {
        count += 1;
        println!("{:?}", a);
    }
    println!("{:?}", count);
}
[2, 1, 0]
[3, 1, 0]
[4, 1, 0]
[5, 1, 0]
[3, 2, 0]
[4, 2, 0]
[5, 2, 0]
[4, 3, 0]
[5, 3, 0]
[5, 4, 0]
[3, 2, 1]
[4, 2, 1]
[5, 2, 1]
[4, 3, 1]
[5, 3, 1]
[5, 4, 1]
[4, 3, 2]
[5, 3, 2]
[5, 4, 2]
[5, 4, 3]
20