基本概念
1、排列
从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
P(n,m)=n(n-1)...(n-m+1)=n!/(n-m)! 特别的,定义0!=1
2、组合
组合数公式是指从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数。用符号c(n,m) 表示。
c(n,m)=p(n,m)/m!=n!/((n-m)!*m!)
3、计算公式
排列算法
递归算法
#include <stdio.h> int n = 0; void swap(int *a, int *b) { int m; m = *a; *a = *b; *b = m; } void perm(int list[], int k, int m) { int i; if(k > m) { for(i = 0; i <= m; i++) printf("%d ", list[i]); printf("\n"); n++; } else { for(i = k; i <= m; i++) { swap(&list[k], &list[i]); perm(list, k + 1, m); swap(&list[k], &list[i]); } } } int main() { int list[] = {1, 2, 3, 4, 5}; perm(list, 0, 4); printf("total:%d\n", n); return 0; }
template <typename T> inline void swap(T* array, unsigned int i, unsigned int j) { T t = array[i]; array[i] = array[j]; array[j] = t; } /* * 递归输出序列的全排列 */ void FullArray(char* array, size_t array_size, unsigned int index) { if(index >= array_size) { for(unsigned int i = 0; i < array_size; ++i) { cout << array[i] << ' '; } cout << '\n'; return; } for(unsigned int i = index; i < array_size; ++i) { swap(array, i, index); FullArray1(array, array_size, index + 1); swap(array, i, index); } }
#include "iostream" using namespace std; void permutation(char* a,int k,int m) { int i,j; if(k == m) { <span style="white-space:pre"> </span>for(i=0;i<=m;i++) <span style="white-space:pre"> </span>cout<<a[i]; cout<<endl; } else { for(j=k;j<=m;j++) { swap(a[j],a[k]); permutation(a,k+1,m); swap(a[j],a[k]); } } } int main(void) { char a[] = "abc"; cout<<a<<"所有全排列的结果为:"<<endl; permutation(a,0,2); system("pause"); return 0; }
#include "iostream" #include "algorithm" using namespace std; void permutation(char* str,int length) { sort(str,str+length); do { for(int i=0;i<length;i++) cout<<str[i]; cout<<endl; }while(next_permutation(str,str+length)); } int main(void) { char str[] = "acb"; cout<<str<<"所有全排列的结果为:"<<endl; permutation(str,3); system("pause"); return 0; }
/// 求从数组a[1..n]中任选m个元素的所有组合。 /// a[1..n]表示候选集,n为候选集大小,n>=m>0。 /// b[1..M]用来存储当前组合中的元素(这里存储的是元素下标), /// 常量M表示满足条件的一个组合中元素的个数,M=m,这两个参数仅用来输出结果。 void combine( int a[], int n, int m, int b[], const int M ) { for(int i=n; i>=m; i--) // 注意这里的循环范围 { b[m-1] = i - 1; if (m > 1) combine(a,i-1,m-1,b,M); else // m == 1, 输出一个组合 { for(int j=M-1; j>=0; j--) cout << a[b[j]] << " "; cout << endl; } } }
#include <iostream> using namespace std; /************************************************************************/ /* num : 需要排列的数组 count : 数组总数 numC: 已经排列的数组 iUse:已经排列的个数 iNull:置0的个数 sum: 总排列数 */ /************************************************************************/ template <class T> void ComBineNum(T *num, const int count, T *numC, int iUse, int* sum) { int iNull = 0; T *newNum = new T[count]; for (int i = 0; i < count; ++i){ memcpy(newNum, num, count); if (newNum[i] == 0){ ++iNull; if (iNull == count){ for (int i = 0; i < count; ++i){ cout << numC[i]; } cout << endl; ++(*sum); return; } continue; } numC[count - iUse] = newNum[i]; newNum[i] = 0; ComBineNum(newNum, count, numC, iUse - 1, sum); } delete[] newNum; } int main() { int sum = 0; const int count = 4; char num[count], pNum[count]; for (int i = 0; i < count; ++i){ num[i] = i + '1'; } ComBineNum<char>(num, count, pNum, count, &sum); cout << "sum :" << sum << endl; sum = 1; for (int i = 1; i <= count; ++i){ sum *= i; } cout << "sum :" << sum << endl; return 0; }
template <class T> void Swap(T& a, T& b) { T c = a; a = b; b = c; } template <class T> void Perm(T list[], int k, int m, int* count) { if (k == m){ for (int i = 0; i < m; ++ i){ cout << list[i]; } cout << endl; ++(*count); } else{ for (int i = k; i < m; ++i){ Swap(list[k], list[i]); Perm(list, k + 1, m, count); Swap(list[i], list[k]); } } } int main() { const int m = 4; int count = 0; int list[m]; for (int i = 0; i < m; ++i){ list[i] = i + 1; } Perm(list, 0, m, &count); cout << count; return 0; }
组合算法
#include<iostream> #include<vector> #include<cstring> using namespace std; #include<assert.h> void Combination(char *string ,int number,vector<char> &result); void Combination(char *string) { assert(string != NULL); vector<char> result; int i , length = strlen(string); for(i = 1 ; i <= length ; ++i) Combination(string , i ,result); } void Combination(char *string ,int number , vector<char> &result) { assert(string != NULL); if(number == 0) { static int num = 1; printf("第%d个组合\t",num++); vector<char>::iterator iter = result.begin(); for( ; iter != result.end() ; ++iter) printf("%c",*iter); printf("\n"); return ; } if(*string == '\0') return ; result.push_back(*string); Combination(string + 1 , number - 1 , result); result.pop_back(); Combination(string + 1 , number , result); } int main(void) { char str[] = "abc"; Combination(str); return 0; }
#include<stdlib.h> #include<String.h> #include<iostream.h> inline void Swap(int*lhs,int*rhs) { int tmp= *lhs; *lhs=*rhs; *rhs=tmp; } void Reverse(int*beg,int*end) { while(beg<end)Swap(beg++,--end); } void Print(int*beg,int*end) { while(beg!=end)cout<<*beg++<<' ';cout<<endl; } inline int Cmp(const void*lhs,const void*rhs) { return *(const int*)rhs - *(const int*)lhs; } void Permutation(int* beg, int* mid, int* end) { int k(0),*p,*q; int i(2); if(end-mid > 1) qsort(mid,end - mid,sizeof(int),Cmp);Print(beg,mid); int* nav = end - 1; while(i) { int* tmp = nav; if(*--nav < *tmp) { int* rmbt = end; while(*--rmbt <= *nav) if(rmbt==mid) { Swap(nav,tmp); nav--; rmbt = end; } Reverse(nav, rmbt+1); qsort(mid, end - mid, sizeof(int), Cmp); Print(beg, mid); nav = end - 1; } i=2; for(q=p=beg;*p<=*++q;p=q) if(q==mid-1)i--; for(q=p=end-1;*p<=*--q;p=q) if(q==mid&&*q<=*beg)i--; } } int main() { int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; Permutation(a,a+3,a+7); return 0; }
参考链接
1、http://dongxicheng.org/structure/permutation-combination/