Permutations & Combinations — The r! Error in Interviews

package io.thecodeforge.math;

import java.math.BigInteger;

public class FactorialCalculator {

    /**
     * Computes n! recursively for n up to 20 (fits within long).
     *
     * Base cases:
     *   0! = 1 — exactly one way to arrange nothing (do nothing)
     *   1! = 1 — trivially one arrangement
     *
     * Do NOT use this for n > 20 — long overflows silently at 21!.
     * For n > 20, use factorialBig() below.
     *
     * The negative-input guard is production hygiene — in an interview
     * context mention it verbally rather than adding a full exception.
     */
    public static long factorial(int n) {
        if (n < 0) throw new IllegalArgumentException("Factorial undefined for negative input: " + n);
        if (n == 0 || n == 1) return 1L;
        return (long) n * factorial(n - 1);
    }

    /**
     * BigInteger version for n > 20.
     * Iterative (no stack overflow risk for large n).
     * Slower than long arithmetic but correct for arbitrarily large n.
     */
    public static BigInteger factorialBig(int n) {
        if (n < 0) throw new IllegalArgumentException("Factorial undefined for negative input: " + n);
        BigInteger result = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }

    public static void main(String[] args) {
        // Show growth rate — critical for understanding overflow risk
        System.out.println("Factorial growth and type boundaries:");
        for (int i = 0; i <= 12; i++) {
            System.out.printf("%2d! = %,d%n", i, factorial(i));
        }
        System.out.println();
        System.out.println("13! = " + factorialBig(13) + "  <- overflows int (max ~2.1B)");
        System.out.println("20! = " + factorialBig(20) + "  <- still fits long");
        System.out.println("21! = " + factorialBig(21) + "  <- overflows long silently");
        System.out.println("25! = " + factorialBig(25) + "  <- BigInteger required");
    }
}

package io.thecodeforge.math;

import java.util.*;

public class PermutationCalculator {

    /**
     * Counts P(n,r) using the top-r-terms cancellation approach.
     *
     * This avoids computing n! and (n-r)! separately (which would overflow
     * for moderate n) by multiplying only the r terms that survive cancellation.
     *
     * P(n,r) = n × (n-1) × ... × (n-r+1)
     *
     * The loop runs from n down to (n-r+1), which is exactly r iterations.
     * Overflow risk: for n=20, r=20, this computes 20! which fits in long.
     * For n > 20, switch to BigInteger.
     *
     * Time: O(r), Space: O(1).
     */
    public static long countPermutations(int n, int r) {
        if (r < 0 || r > n) return 0L;
        if (r == 0) return 1L;
        long result = 1L;
        // Multiply the top r terms of n!: n × (n-1) × ... × (n-r+1)
        for (int i = n; i > n - r; i--) {
            result *= i;
        }
        return result;
    }

    /**
     * Generates all P(n,r) permutations of items using backtracking.
     *
     * Key difference from combination generation:
     *   - No startIndex parameter — every item is considered at every level
     *   - used[] array tracks which items are currently in the selection
     *   - Backtrack by removing from current and resetting used[i] = false
     *
     * Why used[] instead of startIndex?
     * Permutations allow [A,B] and [B,A] as distinct outputs — both must
     * appear. If we used startIndex (the combination approach), we would
     * skip B when A is first, preventing [B,A] from being generated.
     *
     * Time: O(P(n,r) × r) — P(n,r) permutations, each of size r to copy.
     * Space: O(r) recursion depth + O(P(n,r) × r) for stored results.
     */
    public static void generate(
        List<String> items,
        int r,
        List<String> current,
        boolean[] used,
        List<List<String>> results
    ) {
        if (current.size() == r) {
            results.add(new ArrayList<>(current)); // Copy — current is mutated
            return;
        }
        for (int i = 0; i < items.size(); i++) {
            if (!used[i]) {
                used[i] = true;
                current.add(items.get(i));
                generate(items, r, current, used, results);
                // Backtrack: undo the choice made above
                current.remove(current.size() - 1);
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        // Count-only: the formula approach, no generation
        System.out.println("P(8,3) = " + countPermutations(8, 3));  // 336
        System.out.println("P(10,0) = " + countPermutations(10, 0)); // 1 (edge case)
        System.out.println("P(5,5) = " + countPermutations(5, 5));  // 120 = 5!

        // Generate all P(3,2) permutations of [A, B, C]
        List<String> items = List.of("A", "B", "C");
        List<List<String>> results = new ArrayList<>();
        generate(items, 2, new ArrayList<>(), new boolean[items.size()], results);
        System.out.println("\nP(3,2) = " + results.size() + " permutations:");
        results.forEach(System.out::println);
    }
}

package io.thecodeforge.math;

import java.util.*;

public class CombinationCalculator {

    /**
     * Counts C(n,r) using incremental division to prevent overflow.
     *
     * The key insight: instead of computing numerator = n×(n-1)×...×(n-r+1)
     * and denominator = r! separately and dividing at the end (which overflows
     * for moderate n), we interleave the division inside the loop.
     *
     * At step i:
     *   - Multiply by (n - i + 1)  [next numerator term]
     *   - Divide by i               [divide by next denominator term]
     *
     * This works because C(n,r) is always an integer — the intermediate
     * values remain exact integers throughout the loop.
     *
     * Symmetry optimization: C(n,r) = C(n,n-r).
     * If r > n/2, we flip to n-r which has fewer iterations.
     * C(20,18) becomes C(20,2) — 2 iterations instead of 18.
     *
     * Safe for long up to approximately n = 62 with incremental division.
     * For n > 62, use BigInteger variant.
     *
     * Time: O(min(r, n-r)), Space: O(1).
     */
    public static long countCombinations(int n, int r) {
        if (r < 0 || r > n) return 0L;
        if (r == 0 || r == n) return 1L; // C(n,0) = C(n,n) = 1
        if (r > n / 2) r = n - r;         // Symmetry: always use smaller r
        long result = 1L;
        for (int i = 1; i <= r; i++) {
            result *= (n - i + 1); // Next numerator term
            result /= i;           // Divide by next denominator term
            // Division is exact at every step because C(n,r) is always integer
        }
        return result;
    }

    /**
     * Generates all C(n,r) combinations using backtracking with startIndex.
     *
     * The startIndex parameter is the key difference from permutation generation:
     *   - We only consider items at index >= startIndex
     *   - This ensures items are selected in strictly increasing index order
     *   - [A,B] appears exactly once; [B,A] is never generated
     *
     * Why does this prevent duplicates?
     * By enforcing forward-only selection, each unique subset can only be
     * constructed in one order — the one where lower-index items appear first.
     * All other orderings of the same subset are structurally unreachable.
     *
     * Contrast with permutation generation which uses used[] and no startIndex,
     * allowing [A,B] and [B,A] both to appear.
     *
     * Time: O(C(n,r) × r), Space: O(r) stack depth + O(C(n,r) × r) results.
     */
    public static void generate(
        List<String> items,
        int r,
        int startIndex,          // Only consider items at or after this position
        List<String> current,
        List<List<String>> results
    ) {
        if (current.size() == r) {
            results.add(new ArrayList<>(current));
            return;
        }
        for (int i = startIndex; i < items.size(); i++) {
            current.add(items.get(i));
            generate(items, r, i + 1, current, results); // i+1: never revisit earlier items
            current.remove(current.size() - 1);           // Backtrack
        }
    }

    public static void main(String[] args) {
        // Count-only: formula results
        System.out.println("C(8,3) = " + countCombinations(8, 3));   // 56
        System.out.println("C(52,5) = " + countCombinations(52, 5)); // 2,598,960 (poker hands)
        System.out.println("C(20,18) = " + countCombinations(20, 18)); // 190 via symmetry as C(20,2)
        System.out.println("C(10,0) = " + countCombinations(10, 0));  // 1 (edge case)
        System.out.println("C(10,10) = " + countCombinations(10, 10)); // 1 (edge case)

        // Generate all C(4,2) combinations of [A,B,C,D]
        List<String> items = List.of("A", "B", "C", "D");
        List<List<String>> results = new ArrayList<>();
        generate(items, 2, 0, new ArrayList<>(), results);
        System.out.println("\nC(4,2) = " + results.size() + " combinations:");
        results.forEach(System.out::println);
    }
}

package io.thecodeforge.math;

public class TeamFormationSolver {

    /**
     * Solves the compound team formation problem:
     *   - 5 backend engineers, choose exactly 2
     *   - 4 frontend engineers, choose exactly 2
     *   - Order does not matter in either group (combination, not permutation)
     *   - Choices are independent (AND condition → multiply)
     *
     * Demonstrates: decompose first, classify each sub-problem, combine results.
     */
    public static long uniqueTeams(
        int backendPool, int backendNeeded,
        int frontendPool, int frontendNeeded
    ) {
        long backendWays = CombinationCalculator.countCombinations(backendPool, backendNeeded);
        long frontendWays = CombinationCalculator.countCombinations(frontendPool, frontendNeeded);
        // AND condition between independent groups: multiply individual counts
        return backendWays * frontendWays;
    }

    /**
     * Variant with constraint: at least one backend engineer must be the team lead.
     *
     * Direct approach: count teams WITH team lead (fix team lead, choose 1 more from 4)
     * Complementary approach: total teams - teams WITHOUT team lead
     *
     * Both approaches give the same answer. Complementary is often simpler
     * arithmetic for 'at least one' problems — recognize this pattern.
     */
    public static long teamsWithTeamLead(
        int backendPool, int backendNeeded,
        int frontendPool, int frontendNeeded
    ) {
        long totalTeams = uniqueTeams(backendPool, backendNeeded, frontendPool, frontendNeeded);
        // Teams where team lead is NOT selected: choose backendNeeded from (backendPool - 1)
        long teamsWithoutLead = CombinationCalculator.countCombinations(backendPool - 1, backendNeeded)
                               * CombinationCalculator.countCombinations(frontendPool, frontendNeeded);
        // Complementary counting: at least one team lead = total - none
        return totalTeams - teamsWithoutLead;
    }

    public static void main(String[] args) {
        long total = uniqueTeams(5, 2, 4, 2);
        System.out.println("Total unique teams (no constraint): " + total);
        // C(5,2) = 10, C(4,2) = 6, total = 10 x 6 = 60

        long withLead = teamsWithTeamLead(5, 2, 4, 2);
        System.out.println("Teams with at least one team lead: " + withLead);
        // Total 60 - teams without lead C(4,2)*C(4,2) = 6*6 = 36 -> 60 - 36 = 24

        // Additional example: exclusive scenario counting (OR)
        // How many teams have EITHER all backend OR all frontend engineers (4-person team)
        long allBackend = CombinationCalculator.countCombinations(5, 4);
        long allFrontend = CombinationCalculator.countCombinations(4, 4);
        // OR between mutually exclusive scenarios: add individual counts
        System.out.println("4-person teams that are entirely one discipline (OR): "
            + (allBackend + allFrontend));
        // C(5,4)=5, C(4,4)=1, total = 5 + 1 = 6
    }
}