阶乘、排列、组合

阶乘

$x!={\Pi }_{i:1}^{x}i$ 。特殊情况0的阶乘是1。

排列

排列$P_n^m$，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列。第一个元素有n种选择，第二个元素有n-1种选择，$\cdots$
$P_n^m={\Pi }_{i:n-m+1}^{n}i=n!÷(n-m)!$

组合

$C_n^m$ 从n个不同的元素中，任取m（m≤n）个元素为一组。m个元素的顺序有m!种。故：
$$P_n^m\equiv C_n^m\times m!$$

多数组合

以求单词的异构词为例。cnt记录26个字母的出现次数。则异构词的数量：
$total[x]={\sum }_{i:0}^{x-1}cnt[i]$
$异构词的数量={\Pi }_{i:0}^{26}{C}_{totax[26]-total[i]}^{cnt[j]}$
就是每个字符的组合相乘。

封装类

template<class T >
class CFactorial
{
public:
	CFactorial(int n):m_res(n+1){
		m_res[0] = 1;
		for (int i = 1; i <= n; i++) {
			m_res[i] = m_res[i - 1] * i;
		}
	}	
	T Com(int iSel, int iCanSel) {
		return m_res[iCanSel] / m_res[iSel]/ m_res[iCanSel - iSel];
	}
	T Com(const vector<int>& cnt) {
		T biRet = 1;
		int iCanSel = std::accumulate(cnt.begin(), cnt.end(), 0);
		for (int j = 0; j < cnt.size(); j++) {
			biRet *= Com(cnt[j], iCanSel);
			iCanSel -= cnt[j];
		}
		return biRet;
	}
	vector<T> m_res;
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24

帕斯卡法则及容斥原理

【数学归纳法 组合数学】容斥原理

封装类

template<class Result = C1097Int<> >
class CCombination
{
public:
	CCombination()
	{
		m_v.assign(1, vector<Result>(1,1));
	}
	Result Get(int sel, int total)
	{
		assert(sel <= total);
		while (m_v.size() <= total)
		{
			int iSize = m_v.size();
			m_v.emplace_back(iSize + 1, 1);
			for (int i = 1; i < iSize; i++)
			{
				m_v[iSize][i] = m_v[iSize - 1][i] + m_v[iSize - 1][i - 1];
			}
		}
		return m_v[total][sel];
	}
protected:
	vector<vector<Result>> m_v;
};

• 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

阶乘求组合，初始化时：时间复杂度O(n)，查询时：时间复杂度O(3)。
帕斯卡法则求阶乘，初始化时：时间复杂度O(nn)，查询时：时间复杂度O(1)。
阶乘求组合用的乘法，帕斯卡法则用的加法，乘法比加法复杂。

放球问题

放球问题

题解

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。