排列组合 算法实现

文章目录

• Part.I 概念
• • Chap.I 排列
  • Chap.II 组合
• Part.II 代码实现
• • Chap.I 排列组合的计算
  • Chap.II 已知排列组合求 m

Part.I 概念

排列组合的来源和用途就不多 bb 了，下面直接上概念和公式。

Chap.I 排列

从 $n$ 个不同元素中，任取 $m$($m\le n$，$m$ 与 $n$ 均为自然数，下同）个不同的元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列；从 $n$ 个不同元素中取出 $m$($m\le n$）个元素的所有排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数，用符号 $A(n,m)$ 或 A n m A_n^m Anm​ 表示。其计算公式如下：

A n m = n ( n − 1 ) ( n − 2 ) ( n − m + 1 ) = n ! ( n − m ) ! A_n^m=n(n-1)(n-2)(n-m+1)=\frac{n!}{(n-m)!} Anm​=n(n−1)(n−2)(n−m+1)=(n−m)!n!​

Chap.II 组合

从 $n$ 个不同元素中，任取 $m$($m\le n$) 个元素并成一组，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m$($m\le n$) 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数。用符号 $C(n,m)$ 或 C n m C^m_n Cnm​ 表示。其计算公式如下：

C n m = A n m m ! = n ! m ! ( n − m ) ! C^m_n=\frac{A^m_n}{m!}=\frac{n!}{m!(n-m)!} Cnm​=m!Anm​​=m!(n−m)!n!​； C n m = C n ( n − m ) C^m_n=C^{(n-m)}_n Cnm​=Cn(n−m)​

Part.II 代码实现

Chap.I 排列组合的计算

C++ 求 A n m A^m_n Anm​

int An_k(int n, int k) {int ans=1;for(int i=n-k+1;i<n+1;i++) ans*=i;return ans;
}

Python 求 A n m A^m_n Anm​

def An_k(n, k):ans=1for i in range(n-k+1,n+1): ans*=ireturn ans

C++ 求 C n m C^m_n Cnm​

int Ck_n(int n, int k)
{int res = 1;// Since C(n, k) = C(n, n-k)if (k > n - k)k = n - k;// Calculate value of// [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]for (int i = 0; i < k; ++i) {res *= (n - i);res /= (i + 1);}return res;
}

Python 求 C n m C^m_n Cnm​

def Ck_n(n, k):# since C(n, k) = C(n, n - k)if(k > n - k):k = n - k# initialize resultres = 1# Calculate value of# [n * (n-1) *---* (n-k + 1)] / [k * (k-1) *----* 1]for i in range(k):res = res * (n - i)res = res // (i + 1)return res

Chap.II 已知排列组合求 m

已知 A n m A^m_n Anm​ 和 $n$ 求 $m$，因为 A n n = A n ( n − 1 ) A^n_n=A^{(n-1)}_n Ann​=An(n−1)​ ，求出的 $m$ 最大是 $n-1$。

C++ 版

int An_kR(A, n) {if(A==n) return 1;if(A==1) return 0;int m=n;while(A>n) { A/=n--; if(A==n) return m-n+1;}return -1;
}

Python 版

def An_kR(A, n):if A==n: return 1if A==1: return 0m=nwhile A>n:A/=n; n-=1if A==n: return m-n+1return -1

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！