為什么要寫(xiě)這篇文章
排列組合問(wèn)題在數(shù)學(xué)中占有重要的地位向胡，其與概率論也有密切的關(guān)系琐旁。而且排列組合問(wèn)題大量出現(xiàn)在求職筆試面試中倍靡，同時(shí)編寫(xiě)排列組合問(wèn)題碉京，對(duì)于學(xué)習(xí)理解遞歸思想也是很有幫助的厢汹。在此總結(jié)一下排列組合的各種問(wèn)法和變形！
首先谐宙，總結(jié)一下以往常常出現(xiàn)的排列組合題目烫葬，其對(duì)象一般都是整形數(shù)組或者字符類(lèi)型，輸入數(shù)據(jù)一般分為兩類(lèi)：有重復(fù)和無(wú)重復(fù)凡蜻，按照輸出數(shù)據(jù)分類(lèi)搭综，也可以分為有重復(fù)和無(wú)重復(fù)，而且排列問(wèn)題偶爾也會(huì)考非遞歸求解划栓。
排列篇之輸入數(shù)據(jù)無(wú)重復(fù)
1. 輸出數(shù)組a的全排列(不可重復(fù)取)
如a={1,2,3}兑巾。輸出123，132茅姜，213闪朱，231，312钻洒，321
算法思想：假設(shè)輸入數(shù)據(jù)中有n個(gè)不重復(fù)的數(shù)據(jù)奋姿，第一個(gè)元素可以有n中情況，第二個(gè)元素有n-1中情況素标，即可得n個(gè)不重復(fù)的數(shù)據(jù)有n!種全排列称诗。用遞歸法求解該問(wèn)題，第一個(gè)元素從1-n中任取一個(gè)头遭，第二個(gè)元素從剩下的2-n中任取一個(gè)寓免，依次下去直到最后一個(gè)元素，即可求得該全排列计维，詳見(jiàn)下面的算法袜香。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
void permutation2(int a[], int index, int n){
if (index == n){
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
return;
}
for (int i = index; i < n; ++i){
swap(a[index], a[i]);
permutation2(a, index + 1, n);
swap(a[index], a[i]);
}
}
void permutation(int a[], int n){
permutation2(a, 0, n);
}
int main()
{
int a[] = { 1, 5, 9 };
permutation(a, sizeof(a)/sizeof(a[0]));
return 0;
}
2. 輸出數(shù)組a的全排列(可重復(fù)取)
如a={1,2}。輸出11,12,21,22鲫惶。
算法思想：假設(shè)數(shù)組中有n個(gè)元素蜈首，則可重復(fù)取的話(huà)，有n^n種情況，即每個(gè)元素欢策，都有n種選取選擇吆寨。對(duì)于第一個(gè)元素，可以從1-n中選取一個(gè)踩寇，對(duì)于第二個(gè)元素啄清，同樣從1-n中選取一個(gè)，一直到第n個(gè)元素俺孙，詳見(jiàn)下面的算法辣卒。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <utility>
using namespace std;
void permutation2(int a[], int b[], int index, int n){
if (index == n){
for (int i = 0; i < n; ++i)
printf("%d ", b[i]);
printf("\n");
return;
}
for (int i = 0; i < n; ++i){
b[index] = a[i];
permutation2(a, b, index + 1, n);
}
}
void permutation(int a[], int n){
int *b = new int[n];
permutation2(a, b, 0, n);
delete []b;
}
int main()
{
int a[] = { 1,5,9 };
permutation(a, sizeof(a)/sizeof(a[0]));
return 0;
}
3. 輸出數(shù)組a的全排列(非遞歸)
如a={1,2,3}。輸出123,132,213,231,312,321
全排列的非遞歸算法也不唯一睛榄，這里列出一個(gè)最常用的按字典序排列的非遞歸算法添寺。
算法思想：首先對(duì)數(shù)組a進(jìn)行排序，然后依次求解出按字典序的下一個(gè)排列懈费，這里可以采用STL庫(kù)中的next_permutation函數(shù)。當(dāng)然也可以自己實(shí)現(xiàn)next_permutation函數(shù)博脑，leetcode上有一道這樣的練習(xí)題next-permutation憎乙。
代碼如下：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
void permutation(int a[], int n){
sort(a, a+n);
do {
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
} while (next_permutation(a, a + n));
}
int main()
{
int a[] = { 1, 5, 9 };
permutation(a, sizeof(a) / sizeof(a[0]));
return 0;
}
4. 輸出從含n個(gè)數(shù)組a中取m個(gè)數(shù)的所有排列
如a={1,2,3}，m=3, n=2輸出12叉趣，21泞边，13，31疗杉，23阵谚，32.
算法思想：首先從n個(gè)元素中選取m個(gè)，然后對(duì)這m個(gè)元素進(jìn)行全排列烟具。 從n個(gè)元素中選取m個(gè)元素梢什，對(duì)于每個(gè)元素，有選擇和不選擇兩種情況朝聋，用一個(gè)額外的數(shù)組記錄選擇的m個(gè)元素嗡午，然后對(duì)這m個(gè)元素進(jìn)行全排列即可。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
void permutation3(int b[], int index, int m){
if (index == m){
for (int i = 0; i < m; ++i)
printf("%d ", b[i]);
printf("\n");
return;
}
for (int i = index; i < m; ++i){
swap(b[index], b[i]);
permutation3(b, index + 1, m);
swap(b[index], b[i]);
}
}
void permutation2(int a[], int b[], int start1, int m, int start2, int n){
if (start1 == m){
permutation3(b, 0, m);
return;
}
if (m - start1 > n - start2) return;
if (m < start1) return;
if (n < start2) return;
permutation2(a, b, start1, m, start2+1, n);
b[start1] = a[start2];
permutation2(a, b, start1+1, m, start2+1, n);
}
void permutation(int a[], int m, int n){
int *b = new int[m];
permutation2(a, b, 0, m, 0, n);
delete[] b;
}
int main()
{
int a[] = { 1, 5, 9, 11};
int m = 3;
permutation(a, m, sizeof(a) / sizeof(a[0]));
return 0;
}
排列篇之輸入數(shù)據(jù)有重復(fù)
例如a={1,3,2,3}冀痕，其中數(shù)字3出現(xiàn)了兩次荔睹，用上面的方法進(jìn)行求解會(huì)造成重復(fù)輸出。
5. 輸出含重復(fù)元素?cái)?shù)組的全排列(遞歸)
例如a={1,3,2,3}言蛇，則其全排列為1233,1323,3123,1332,3132,2133,2313,3213,2331,3231,3312,3321
算法分析： 數(shù)組a中有n個(gè)元素僻他，元素可表述為： a1,a1,...a1, a2,a2,...a2,.......,am,am,...am。則可以證明不重復(fù)的排列種類(lèi)的數(shù)目為：n!/(n1!*n2!*...*nm!)腊尚。將這n個(gè)元素做全排列吨拗，這里只要限制將要選擇的元素大小必須大于原來(lái)已經(jīng)選擇的元素大小即可達(dá)到目標(biāo)，詳見(jiàn)程序(含注釋)。
#include <stdio.h>
#define N 5
void arrange(int rec[], int used[], int depth);
void write(int rec[], int maxdepth);
//int a[N] = { 1, 1, 5, 5, 9 }; //這些值必須升序排列且大于0
int a[] = { 1, 1, 1, 5, 5 };
int count = 0;
int main()
{
int rec[N + 1] = { 0 }, used[N + 1] = { 0 };
arrange(rec, used, 0);
printf("\ncount=%d ", count);
getchar();
return 0;
}
void write(int rec[])
{
int i;
for (i = 0; i <N; i++)
printf("%d ", a[rec[i]]);
printf("\n");
count++;
}
void arrange(int rec[], int used[], int depth)
{
int i, found_num;
if (depth>= N) write(rec); //找到了一個(gè)可行解丢胚，輸出
else
{
found_num = 0; //增加這個(gè)變量記錄原來(lái)本結(jié)點(diǎn)存儲(chǔ)的數(shù)字
for (i = 0; i <N; i++) // 搜索該結(jié)點(diǎn)的孩子結(jié)點(diǎn)
{//如果該下標(biāo)在前面還沒(méi)有使用過(guò)翩瓜，且該下標(biāo)所指示的數(shù)字比
//原先所放置的數(shù)字要大，則是一個(gè)部分解
if (used[i] == 0 && a[i]> found_num)
{
rec[depth] = i; //記錄下該結(jié)點(diǎn)放置的下標(biāo)
found_num = a[i]; //記錄下本結(jié)點(diǎn)存放的數(shù)字
used[i] = 1; // 標(biāo)記該下標(biāo)已經(jīng)被使用
arrange(rec, used, depth + 1); // 擴(kuò)展携龟，進(jìn)入孩子結(jié)點(diǎn)繼續(xù)搜索
used[i] = 0; //退回來(lái)后要清除本結(jié)點(diǎn)所記錄下標(biāo)的使用記錄
}
}
}
}
另一種算法：我們改進(jìn)一下1的算法兔跌，在for中判斷是否有包含重復(fù)元素，也就是index和i之間是否有和a[i]相等的值峡蟋，比如對(duì)于2313這個(gè)數(shù)列坟桅，當(dāng)index=0(a[index] = 2),i=3(a[i] = 3)的時(shí)候,如果要交換這兩個(gè)數(shù)變成3312的話(huà)就是計(jì)算重復(fù)了，因?yàn)樗鼈冎g有1個(gè)3蕊蝗，當(dāng)i=1的時(shí)候仅乓，它已經(jīng)轉(zhuǎn)換過(guò)3312了。所以加一個(gè)函數(shù)判斷中間有沒(méi)有包含重復(fù)元素蓬戚，如有沒(méi)有重復(fù)元素夸楣，再做交換；代碼如下所示：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int total = 0;
bool contains(int a[], int index, int i){
for (int k = index; k < i; ++k)
if (a[k] == a[i])
return true;
return false;
}
void permutation2(int a[], int index, int n){
if (index == n){
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
total++;
return;
}
for (int i = index; i < n; ++i){
if (contains(a, index, i))
continue;
swap(a[index], a[i]);
permutation2(a, index + 1, n);
swap(a[index], a[i]);
}
}
void permutation(int a[], int n){
permutation2(a, 0, n);
}
int main()
{
int a[] = { 1, 5, 5, 5, 9, 9 };
total = 0;
permutation(a, sizeof(a) / sizeof(a[0]));
printf("total: %d\n", total);
return 0;
}
6. 輸出含重復(fù)元素?cái)?shù)組的全排列(非遞歸)
與算法3相同子漩，使用next_permutation函數(shù)即可豫喧！
組合篇之輸入數(shù)據(jù)無(wú)重復(fù)
1. 輸入一個(gè)數(shù)組a和target，從數(shù)列數(shù)組a中任取幾個(gè)數(shù)幢泼，使其和等于target紧显，要求將其中所有的可能組合列出來(lái)（不可重復(fù)取）缕棵。
算法分析：這是一個(gè)典型的01背包問(wèn)題孵班， 對(duì)于數(shù)組中的沒(méi)一個(gè)數(shù)，有取和不取兩種方式招驴，因?yàn)樾枰敵鏊械那闆r篙程，所以此處用回溯，不用動(dòng)規(guī)求解忽匈。
動(dòng)規(guī)求解數(shù)組a中任取幾個(gè)數(shù)房午，其和為target的數(shù)目：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int solve(int a[], int n, int target)
{
int *tmp = new int[target + 1];
memset(tmp, 0, (target + 1)*sizeof(*tmp));
for (int i = 0; i < n; ++i){
if (a[i]>target) break;
for (int j = target - a[i]; j >= 1; --j){
if (tmp[j] > 0)
tmp[j + a[i]]++;
}
tmp[a[i]]++;
}
int x = tmp[target];
delete[] tmp;
return x;
}
int main()
{
int target;
int a[] = { 1, 3, 4, 6, 7 };
sort(a, a + sizeof(a) / sizeof(a[0]));
while (cin >> target){
cout << "total: " << solve(a, sizeof(a)/sizeof(a[0]), target) << endl;
}
return 0;
}
回溯法求出所有滿(mǎn)足要求的情況：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
void permutation(int a[], int index, int n, int b[], int num, int target)
{//回溯求解所有的情況
if (target == 0){
for (int i = 0; i < num; ++i)
printf("%d ", b[i]);
printf("\n");
return;
}
if (index >= n) return;
permutation(a, index+1, n, b, num, target);
b[num] = a[index];
permutation(a, index + 1, n, b, num+1, target-a[index]);
}
int main()
{
int target;
int a[] = { 1, 3, 4, 6, 7 };
int *b = new int[sizeof(a) / sizeof(a[0])];
sort(a, a + sizeof(a) / sizeof(a[0]));
while (cin >> target){
permutation(a, 0, sizeof(a) / sizeof(a[0]), b, 0, target);
}
delete[] b;
return 0;
}
2. 輸入兩個(gè)整數(shù) n 和 m，從數(shù)列1丹允，2郭厌，3.......n 中 隨意取幾個(gè)數(shù)，使其和等于 m ,要求將其中所有的可能組合列出來(lái)（可重復(fù)鹊癖巍）
算法分析： 計(jì)算出每個(gè)元素可以加入的次數(shù)折柠，分別為A,B,C....， 則第一個(gè)元素可加入0A次批狐，第二個(gè)元素加入0B次扇售，一直遞歸下去
詳見(jiàn)下面的代碼：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
void permutation(int a[], int index, int n, vector<int> vec, int target)
{//回溯求解所有的情況
if (target == 0){
for (auto it = vec.begin(); it != vec.end(); ++it)
cout << *it << " ";
printf("\n");
return;
}
if (index >= n) return;
int t = target / a[index];
for (int i = 0; i <= t; ++i){
permutation(a, index+1, n, vec, target);
vec.push_back(a[index]);
target = target - a[index];
}
}
int main()
{
int target;
int a[] = { 1, 3, 4, 6, 7 };
vector<int> vec;
sort(a, a + sizeof(a) / sizeof(a[0]));
while (cin >> target){
permutation(a, 0, sizeof(a) / sizeof(a[0]), vec, target);
}
return 0;
}
上面所述已經(jīng)涉及到了排列組合常見(jiàn)的問(wèn)題前塔，其他的情況詳見(jiàn)參考資料！
