Combinatorics and Permutations

Unique Paths (LeetCode 62)

The total steps are $(m-1) + (n-1)$. We need to choose $m-1$ downward steps out of the total. Formula: $C(m+n-2, \min(m,n)-1)$. Use iterative multiplication to prevent intermediate overflow.

public int uniquePaths(int m, int n) {
    long result = 1;
    int k = Math.min(m - 1, n - 1);
    int total = m + n - 2;
    for (int i = 1; i <= k; i++) {
        // Combination formula: C(n, k) = C(n, k-1) * (n-k+1) / k
        result = result * (total - i + 1) / i;
    }
    return (int) result;
}

Permutation Sequence (LeetCode 60)

Find the $k$-th permutation using Factorial Number System. We determine digits one by one based on how many permutations start with each digit.

public String getPermutation(int n, int k) {
    int[] factorials = new int[n + 1];
    factorials[0] = 1;
    for (int i = 1; i <= n; i++) factorials[i] = factorials[i - 1] * i;
    
    List<Integer> numbers = new ArrayList<>();
    for (int i = 1; i <= n; i++) numbers.add(i);
    
    k--; // Convert to 0-indexed
    StringBuilder sb = new StringBuilder();
    
    for (int i = n; i >= 1; i--) {
        int index = k / factorials[i - 1];
        sb.append(numbers.remove(index));
        k %= factorials[i - 1];
    }
    return sb.toString();
}

Next Permutation (LeetCode 31)

Find the lexicographically next greater permutation.

1. Find the first decreasing element from the right (nums[i] < nums[i+1]).
2. If it exists, find the smallest element to its right that is larger than nums[i] and swap them.
3. Reverse the portion to the right of $i$ to get the smallest possible sequence.

public void nextPermutation(int[] nums) {
    int n = nums.length;
    int i = n - 2;
    // Find first decreasing element
    while (i >= 0 && nums[i] >= nums[i+1]) i--;
    
    if (i >= 0) {
        int j = n - 1;
        // Find smallest element > nums[i]
        while (nums[j] <= nums[i]) j--;
        swap(nums, i, j);
    }
    // Reverse everything after i
    reverse(nums, i + 1, n - 1);
}

private void reverse(int[] nums, int l, int r) {
    while (l < r) swap(nums, l++, r--);
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

筋