排列数公式定义

从n个不同元素中取出m个元素进行排列，其排列数计算公式为：

$$ P_n^m = \frac{n!}{(n-m)!} $$

其中：

• n 表示总元素个数
• m 表示要排列的元素个数
• n! 表示n的阶乘，即 n × (n-1) × (n-2) × ... × 2 × 1

特殊情况

当 m = n 时，公式简化为：

$$ P_n^n = n! $$

当 m = 0 时：

$$ P_n^0 = 1 $$

示例

从5个元素中取3个元素排列的方法数为：

$$ P_5^3 = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{5 × 4 × 3 × 2!}{2!} = 60 $$

public class PermutationCalculator {

    /**
     * 计算排列数 A(n, k) = n * (n - 1) * ... * (n - k + 1)
     * @param n 总数
     * @param k 选取数
     * @return 排列数 A(n, k)，若中间值溢出 long 返回 -1
     */
    public static long permutation(int n, int k) {
        if (k < 0 || n < 0 || k > n) {
            throw new IllegalArgumentException("参数不合法: n >= k >= 0");
        }

        long result = 1L;
        for (int i = 0; i < k; i++) {
            result *= (n - i);
            if (result < 0) { // 说明溢出
                return -1;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(permutation(10, 3));   // 输出: 720
        System.out.println(permutation(20, 10));  // 输出: 670442572800L
        System.out.println(permutation(100, 20)); // 可能溢出，返回 -1
    }
}

<aside> 💡

更大规模考虑使用 BigInteger

</aside>