Generating Elementary Combinatorial Object

genElCombObj.ts

// Implementation inspired by:
// https://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf
// https://docs.microsoft.com/en-us/previous-versions/visualstudio/aa289166(v=vs.70)

function subsetLexCharacteristicVector(n: number, T: Set<number>): Array<0|1> {
    const TX: Array<0|1> = Array.from({ length: n });
    let i = 0;
    for (i; i < n; ++i) {
        TX[i] = T.has(i) ? 1 : 0;
    }
    return TX;
}

function subsetLexRank(n: number, T: Set<number>): number {
    let i = 0,
        r = 0;
    for (i; i < n; ++i) {
        r *= 2;
        if (T.has(i)) {
            ++r;
        }
    }
    return r;
}

function subsetLexUnrank(n: number, r: number): Set<number> {
    const T: Array<number> = [];
    let i = n - 1;
    for (i; i >= 0; --i) {
        if (r % 2 === 1) {
            T.unshift(i);
        }
        r = Math.floor(r / 2);
    }
    return new Set(T);
}

function subsetLexSuccessor(n: number, T: Set<number>): Set<number> {
    let U = new Set(Array.from(T));
    const fixedN = n - 1;
    let i = 0;
    while (i < n && U.has(fixedN - i)) {
        U.delete(fixedN - i);
        ++i;
    }
    if (i < n) {
        U.add(fixedN - i);
    }
    return U;
}

function kSubsetLexSuccessor(T: Set<number>, k: number, n: number): Set<number> {
    let U = Array.from(T);
    let i = k - 1, j;
    while (i > 0 && U[i] === n - k + i) {
        --i;
    }
    ++U[i];
    for (j = i; j < k - 1; ++j) {
        U[j + 1] = U[j] + 1;
    }
    return new Set(U);
}

function factorial(n: number): number {
    if (n <= 1) {
        return 1;
    }
    let i = 2, acc = 1;
    for (i; i <= n; ++i) {
        acc *= i;
    }
    return acc;
}

function countCombinations(n: number, k: number): number {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

function generateCombinations(n: number, k: number): Array<Set<number>> {
    const numberOfSubsets = countCombinations(n, k);
    const combinations: Array<Set<number>> = [];
    let i = 0;
    let subset: Set<number>;
    subset = new Set(Array.from({ length: k }, (_, idx) => idx));
    for (i; i < numberOfSubsets; ++i) {
        combinations.push(subset);
        subset = kSubsetLexSuccessor(subset, k, n);
    }
    return combinations;
}

// TEST

const n = 5;
const k = 3;
const combinations = generateCombinations(n, k);

console.log(combinations);