← All posts

Algorithms / Generate repeated combinatorial

The algorithm is simple:

1. Find the right most element less than n
2. Increase it
3. Set the other right the same

It can be implemented as following:

const next = (r) => {
    let n = r.length;
    for (let i = n - 1; i >= 0; i--) {
        if (r[i] < n) {
            r[i]++;
            for (let j = i; j < n; j++) {
                r[j] = r[i];
            }
            return r;
        }
    }
     return null;
};

And here’s how we would use it:

let gen = next([0, 0, 0, 0]);
while (gen != null) {
    console.log(gen);
    gen = next(gen);
}