递归和排列组合

图(图片来自网络)

工具类

代码如下：

import java.util.HashMap;

/**
 * FPC		阶乘、排列、组合
 * Factorial	阶乘(n中取n)
 * Permutation	排列(n中取r，顺序不同的算多种)
 * Combination	组合(n中取r，不考虑顺序)。将元素集相同但顺序不同的情况归为一类。
 */
class FPC {

	// 缓存
	private static HashMap<Integer, Integer> map = new HashMap<>();
	static {
		map.put(0, 1);	// 递归的终结点。
	};
	// 阶乘：f(n) = n * (n - 1) * (n - 2) * ... * 1
	public static int getFactorial(int n) {
		if (map.containsKey(n)) {
			return map.get(n);	// 查询缓存
		}
		int result = n * getFactorial(n - 1);	// 递归
		map.put(n, result);		// 缓存计算得到的新值
		return result;
	}

	// 排列：n中取m。 p(n, r) = n * (n - 1) * (n - 2) * ... * (n - r + 1)
	public static int getPnr(int n, int r) {
		return getFactorial(n) / getFactorial(n - r);
	}

	// 组合：n中取r(不考虑顺序)。
	public static int getCnr(int n, int r) {
		int another = n - r;
		if (another < r) {
			r = another;	// C(n, r) = C(n, n-r)
		}
		return getPnr(n, r) / getFactorial(r);
	}

	// 查看缓存
	// public static void show() {
	// 	for (Map.Entry entry : map.entrySet()) {
	// 		System.out.println(entry);
	// 	}
	// }
}

调用测试

public static void main(String[] args) {
	System.out.println(FPC.getFactorial(10));
	System.out.println(FPC.getFactorial(6));
	System.out.println(FPC.getPnr(5, 3));
	System.out.println(FPC.getPnr(5, 2));
	System.out.println(FPC.getCnr(5, 3));
	System.out.println(FPC.getCnr(5, 2));
}

输出结果：

3628800
720
60
20
10
10