java求排列组合数

发表于 | 分类于

排列数公式

$A^m_n=A(n,m)=n(n-1)(n-2)\cdot(n-m+1)=\dfrac{n!}{(n-m)!}$

组合数公式

$$C^m_n=C(n,m)=\dfrac{A^m_n}{A^m_m}=\dfrac{A(n,m)}{A(m,m)}\\
=\dfrac{n(n-1)(n-2)\cdots(n-m+1)}{m!}=\dfrac{n!}{m!(n-m)!}$$
规定：$C(n,0)=1$

组合数性质

即从m个不同元素中取出n个元素的组合数=从m个不同元素中取出(m-n)个元素的组合数；运用互补性质可以简化组合数的计算量。
$$C_n^m=C_n^{n-m}$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package com.lan.MathFunction;
//求排列数组合数
public class Test
{
	// 求排列数 A(n,m) n>m
	public static int A(int n, int m)
	{
		int result = 1;
		// 循环m次,如A(6,2)需要循环2次，6*5
		for (int i = m; i > 0; i--)
		{
			result *= n;
			n--;// 下一次减一
		}
		return result;
	}
	// 求组合数，这个也不需要了。定义式，不使用互补率
	public static int C2(int n, int m)
	{
		// int denominator=factorial(up);//分母up的阶乘
		// 分母
		int denominator = A(m, m);// A(6,6)就是求6*5*4*3*2*1,也就是求6的阶乘
		// 分子
		int numerator = A(n, m);// 分子的排列数
		return numerator / denominator;
	}
	public static int C(int n, int m)// 应用组合数的互补率简化计算量
	{
		int helf = n / 2;
		if (m > helf)
		{
			System.out.print(m + "---->");
			m = n - m;
			System.out.print(m + "\n");
		}
		// 分子的排列数
		int numerator = A(n, m);
		// 分母的排列数
		int denominator = A(m, m);
		return numerator / denominator;
	}
	public static void main(String[] args)
	{
		for (int i = 1; i <= 6; i++)
		{
			System.out.println("A(6," + i + ")=" + A(6, i));
		}
		for (int i = 1; i <= 6; i++)
		{
			System.out.println("C(6," + i + ")=" + C(6, i));
		}
		System.out.println("C(6,5)=" + C(6, 5));// 6
	}
}

结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
A(6,1)=6
A(6,2)=30
A(6,3)=120
A(6,4)=360
A(6,5)=720
A(6,6)=720
C(6,1)=6
C(6,2)=15
C(6,3)=20
4---->2
C(6,4)=15
5---->1
C(6,5)=6
6---->0
C(6,6)=1
5---->1
C(6,5)=6

参考文档

https://wenku.baidu.com/view/39f79decb04e852458fb770bf78a6529647d350f.html

本文链接: java求排列组合数

0%