Integer partitions with internal iteration

integer-partitions.rs

// Compare to https://gist.github.com/bsidhom/224b1c343bc18e4c351f3ba6a3655dba, which uses external
// iterators. This is _substantially_ faster than the JavaScript variant (unsurprisingly):
// https://gist.github.com/bsidhom/53b13d54f0059086d9b6c4e20fd8d42a
fn main() {
    let mut n = 0;
    partitions(100, |_p| {
        n += 1;
        if n % 1000000 == 0 {
            println!("{n}");
        }
    });
    println!("{n}");
}

fn partitions<F>(n: u32, f: F)
where
    F: FnMut(&[u32]),
{
    fn rec<F>(n: u32, k: u32, prefix: &mut Vec<u32>, f: &mut F)
    where
        F: FnMut(&[u32]),
    {
        let mut i = k;
        while 2 * i <= n {
            prefix.push(i);
            rec(n - i, i, prefix, f);
            prefix.pop();
            i += 1;
        }
        prefix.push(n);
        f(prefix);
        prefix.pop();
    }
    let mut prefix = vec![];
    let mut f = f;
    rec(n, 1, &mut prefix, &mut f);
}