Permutations and Combinations Explained for Coding Interviews

public class FactorialCalculator {

    /**
     * Calculates n! recursively.
     * Base case: 0! = 1 (by mathematical convention — one way to arrange nothing).
     * Recursive case: n! = n * (n-1)!
     */
    public static long factorial(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Factorial is undefined for negative numbers.");
        }
        if (n == 0 || n == 1) {
            return 1; // Both 0! and 1! equal 1
        }
        return n * factorial(n - 1); // Each call reduces the problem by one step
    }

    public static void main(String[] args) {
        // Print factorials 0 through 10 to build intuition for scale
        for (int number = 0; number <= 10; number++) {
            System.out.printf("%2d! = %,d%n", number, factorial(number));
        }

        // Demonstrate the explosive growth that makes brute force impractical
        System.out.println("\n--- Why formulas matter ---");
        System.out.printf("Arrangements of a 20-item list: %,d%n", factorial(20));
        System.out.println("That's over 2 quintillion — listing them is impossible.");
    }
}

import java.util.ArrayList;
import java.util.List;

public class PermutationCalculator {

    /**
     * Calculates P(totalItems, chooseCount) — the number of ordered arrangements.
     * Formula: totalItems! / (totalItems - chooseCount)!
     * We compute it iteratively to avoid unnecessary large factorial calculations.
     */
    public static long countPermutations(int totalItems, int chooseCount) {
        if (chooseCount > totalItems) {
            return 0; // Can't choose more items than exist
        }
        long result = 1;
        // Multiply from totalItems down to (totalItems - chooseCount + 1)
        // e.g. P(8,3) = 8 * 7 * 6  — no need to compute 8! or 5!
        for (int i = totalItems; i > totalItems - chooseCount; i--) {
            result *= i;
        }
        return result;
    }

    /**
     * Generates all actual permutations of 'chooseCount' items from the source list.
     * Uses backtracking: pick one item, recurse on the rest, then un-pick (backtrack).
     */
    public static void generatePermutations(
            List<String> sourceItems,
            int chooseCount,
            List<String> currentPerm,
            boolean[] usedFlags,
            List<List<String>> allResults) {

        if (currentPerm.size() == chooseCount) {
            allResults.add(new ArrayList<>(currentPerm)); // Save a copy of this valid arrangement
            return;
        }

        for (int i = 0; i < sourceItems.size(); i++) {
            if (!usedFlags[i]) {                          // Only pick items not already in the current permutation
                usedFlags[i] = true;                     // Mark as used
                currentPerm.add(sourceItems.get(i));     // Add to current arrangement
                generatePermutations(sourceItems, chooseCount, currentPerm, usedFlags, allResults);
                currentPerm.remove(currentPerm.size() - 1); // Backtrack — remove last item
                usedFlags[i] = false;                    // Un-mark so it's available in other branches
            }
        }
    }

    public static void main(String[] args) {
        // --- Count only ---
        System.out.println("=== Count Permutations ===");
        System.out.println("P(8,3) — assigning gold/silver/bronze from 8 athletes: "
                + countPermutations(8, 3));  // Expected: 336
        System.out.println("P(10,4) — 4-digit PINs with no repeated digits: "
                + countPermutations(10, 4)); // Expected: 5040
        System.out.println("P(5,5) — all arrangements of 5 items (= 5!): "
                + countPermutations(5, 5));  // Expected: 120

        // --- Generate actual arrangements ---
        System.out.println("\n=== Generate All P(3,2) Permutations of [A, B, C] ===");
        List<String> medals = List.of("Alice", "Bob", "Carol");
        List<List<String>> permutations = new ArrayList<>();
        boolean[] used = new boolean[medals.size()];

        generatePermutations(medals, 2, new ArrayList<>(), used, permutations);

        for (List<String> perm : permutations) {
            System.out.println(perm);
        }
        System.out.println("Total arrangements: " + permutations.size()); // Should match P(3,2) = 6
    }
}

import java.util.ArrayList;
import java.util.List;

public class CombinationCalculator {

    /**
     * Calculates C(totalItems, chooseCount) using the optimised iterative approach.
     * We apply the symmetry rule first: if chooseCount > totalItems/2, flip it.
     * Then we compute the numerator and denominator together to stay within long range.
     */
    public static long countCombinations(int totalItems, int chooseCount) {
        if (chooseCount > totalItems) return 0;
        if (chooseCount == 0 || chooseCount == totalItems) return 1;

        // Symmetry optimisation: C(n, r) == C(n, n-r)
        // Always calculate using the smaller of the two to minimise multiplications
        if (chooseCount > totalItems - chooseCount) {
            chooseCount = totalItems - chooseCount;
        }

        long result = 1;
        for (int i = 0; i < chooseCount; i++) {
            result *= (totalItems - i);  // Numerator terms: n, n-1, n-2 ...
            result /= (i + 1);           // Divide incrementally to keep numbers small
            // Dividing here (not after) prevents long overflow on large inputs
        }
        return result;
    }

    /**
     * Generates all actual combinations using backtracking.
     * Key difference from permutation generator: we pass a 'startIndex' so we
     * never look back at already-visited items, eliminating duplicate groups.
     */
    public static void generateCombinations(
            List<String> sourceItems,
            int chooseCount,
            int startIndex,
            List<String> currentGroup,
            List<List<String>> allResults) {

        if (currentGroup.size() == chooseCount) {
            allResults.add(new ArrayList<>(currentGroup)); // Found a valid group
            return;
        }

        for (int i = startIndex; i < sourceItems.size(); i++) {
            currentGroup.add(sourceItems.get(i));  // Add this item to the group
            generateCombinations(sourceItems, chooseCount, i + 1, currentGroup, allResults);
            // i+1 means we never revisit earlier items — [A,B] and [B,A] won't both appear
            currentGroup.remove(currentGroup.size() - 1); // Backtrack
        }
    }

    public static void main(String[] args) {
        // --- Count only ---
        System.out.println("=== Count Combinations ===");
        System.out.println("C(8,3) — choose 3 devs from 8 candidates: "
                + countCombinations(8, 3));  // Expected: 56
        System.out.println("C(52,5) — 5-card poker hand from 52-card deck: "
                + countCombinations(52, 5)); // Expected: 2598960
        System.out.println("C(20,18) using symmetry [=C(20,2)]: "
                + countCombinations(20, 18)); // Expected: 190 — fast due to symmetry flip

        // --- Generate actual groups ---
        System.out.println("\n=== Generate All C(4,2) Combinations of [W, X, Y, Z] ===");
        List<String> candidates = List.of("Wren", "Xander", "Yuki", "Zoe");
        List<List<String>> combinations = new ArrayList<>();

        generateCombinations(candidates, 2, 0, new ArrayList<>(), combinations);

        for (List<String> group : combinations) {
            System.out.println(group);
        }
        System.out.println("Total groups: " + combinations.size()); // Should match C(4,2) = 6
    }
}

public class TeamFormationSolver {

    /**
     * Optimised C(n, r) — same logic as before, extracted for reuse.
     */
    public static long combinations(int totalItems, int chooseCount) {
        if (chooseCount > totalItems || chooseCount < 0) return 0;
        if (chooseCount == 0 || chooseCount == totalItems) return 1;
        if (chooseCount > totalItems - chooseCount) {
            chooseCount = totalItems - chooseCount; // Symmetry shortcut
        }
        long result = 1;
        for (int i = 0; i < chooseCount; i++) {
            result *= (totalItems - i);
            result /= (i + 1);
        }
        return result;
    }

    public static void main(String[] args) {
        // ─────────────────────────────────────────────────────────
        // Problem 1: Mixed team formation
        // 5 backend engineers, 4 frontend engineers.
        // Form a team of exactly 2 backend + 2 frontend.
        // ─────────────────────────────────────────────────────────
        int backendEngineers   = 5;
        int backendNeeded      = 2;
        int frontendEngineers  = 4;
        int frontendNeeded     = 2;

        long backendGroups  = combinations(backendEngineers, backendNeeded);  // C(5,2) = 10
        long frontendGroups = combinations(frontendEngineers, frontendNeeded); // C(4,2) = 6

        // The choices are independent — multiply them (multiplication principle)
        long totalTeams = backendGroups * frontendGroups;

        System.out.println("=== Problem 1: Mixed Team Formation ===");
        System.out.printf("Backend groups  C(%d,%d) = %d%n", backendEngineers, backendNeeded, backendGroups);
        System.out.printf("Frontend groups C(%d,%d) = %d%n", frontendEngineers, frontendNeeded, frontendGroups);
        System.out.printf("Total unique teams = %d × %d = %d%n%n", backendGroups, frontendGroups, totalTeams);

        // ─────────────────────────────────────────────────────────
        // Problem 2: Committee with a required member
        // Choose a committee of 4 from 10 people, but Priya MUST be included.
        // If Priya is fixed, we only need to choose 3 more from the remaining 9.
        // ─────────────────────────────────────────────────────────
        int totalCandidates      = 10;
        int committeeSize        = 4;
        int remainingAfterPriya  = totalCandidates - 1; // Priya is fixed
        int slotsToFill          = committeeSize - 1;   // One slot already filled

        long committeesWithPriya = combinations(remainingAfterPriya, slotsToFill); // C(9,3)

        System.out.println("=== Problem 2: Required Member ===");
        System.out.printf("Priya is fixed. Choose %d from remaining %d: C(%d,%d) = %d%n",
                slotsToFill, remainingAfterPriya, remainingAfterPriya, slotsToFill, committeesWithPriya);

        // ─────────────────────────────────────────────────────────
        // Problem 3: Arrange a password — 3 letters from {A-E} + 2 digits from {1-5}
        // Letters chosen with order mattering (P), digits chosen with order mattering (P)
        // Then multiply for the combined arrangement count.
        // ─────────────────────────────────────────────────────────
        long letterArrangements = permutations(5, 3); // P(5,3) = 60
        long digitArrangements  = permutations(5, 2); // P(5,2) = 20
        long passwordCount      = letterArrangements * digitArrangements;

        System.out.println("\n=== Problem 3: Mixed Password (ordered) ===");
        System.out.printf("Letter arrangements P(5,3) = %d%n", letterArrangements);
        System.out.printf("Digit arrangements  P(5,2) = %d%n", digitArrangements);
        System.out.printf("Total passwords = %d × %d = %d%n", letterArrangements, digitArrangements, passwordCount);
    }

    public static long permutations(int totalItems, int chooseCount) {
        if (chooseCount > totalItems) return 0;
        long result = 1;
        for (int i = totalItems; i > totalItems - chooseCount; i--) {
            result *= i; // Multiply descending: n, n-1, ..., n-r+1
        }
        return result;
    }
}