1.什麼是數學中的組合？
和排列不同的是，在組合中取出元素的順序則不在考慮之中。從個元素中取出個元素，這個元素可能出現的組合數的總數量為：
以1,2,3,4,5中選2個數為例，總共的組合為：
1,2
1,3
1,4
1,5
2,3
2,4
2,5
3,4
3,5
4,5
2.在計算機中如何高效的實現排列算法？
乍一看，這個問題並不簡單。有遞歸的實現方式，效率較低，還比較難，先不考慮。我們注意到一種以二進制的思想的實現方式，比較高效，來講講它。
首先還是需要講下上次的排列算法中比較高效的實現方式（http://www.linuxidc.com/Linux/2014-03/98363.htm），就是把1,2,3的全排列，換算成求一個三位數，由1,2,3組成，從小到大所有的可能性。
123 < 132 < 213 < 231 < 312 < 321
我們還是以1,2,3,4,5中選2個數為例。
我們這次的排列非常的像，我們用一個五個數的數組表示一個5位數的二進制數字，(其中1表示選中該數字，0則不是)這樣用一個二進制數來表示一個排列。如果這個二進制遍歷所有的可能性(0~31)，且只有兩個1組成的話，就是一個我們想要的排列結果。這裡我們換成十進制從左往右換算，發現剛好是從小到大。
1,2 (1,1,0,0,0) -- 3(十進制)
1,3 (1,0,1,0,0) -- 5
2,3 (0,1,1,0,0) -- 6
1,4 (1,0,0,1,0) -- 9
2,4 (0,1,0,1,0) -- 10
3,4 (0,0,1,1,0) -- 12
1,5 (1,0,0,0,1) -- 17
2,5 (0,1,0,0,1) -- 18
3,5 (0,0,1,0,1) -- 20
4,5 (0,0,0,1,1) -- 24
如何用代碼實現呢？
需要用以下策略：
1.m 選 n， 初始化m個數，它們都是0，前n個都變成1，表示最小的二進制。
2.如何找到下一個較大的數呢？因為我們這裡的二進制是從左往右，所以，當發現一個1,0時，我們把它改成0,1的時候，這個數就變大了！
3.根據策略2的話(0,1,1,0,0)--6下一個二進制數應該是(0,1,0,1,0)--10，但是比(0,1,1,0,0)要大的下一個數應該是(1,0,0,1,0)--9。所以
我們要把1,0換成0,1的時候，還要把0,1中0的前面所有1都移到最前面，這樣才是最小的數，大家理解下這句。因為我們的二進制是從左往右的。
代碼如下，非常簡短。
// MyCombination.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printResult(vector<int>& vecInt, int t[]){
for(int i = 0; i < vecInt.size(); ++i){
if(vecInt[i] == 1){
cout << t[i] << " ";
}
}
cout << endl;
}
bool compare(int a, int b){
if(a > b){
return true;
}else{
return false;
}
}
void combination(int t[], int c, int total){
//initial first combination like:1,1,0,0,0
vector<int> vecInt(total,0);
for(int i = 0; i < c; ++i){
vecInt[i] = 1;
}
printResult(vecInt, t);
for(int i = 0; i < total - 1; ++i){
if(vecInt[i] == 1 && vecInt[i+1] == 0){
//1. first exchange 1 and 0 to 0 1
swap(vecInt[i], vecInt[i+1]);
//2.move all 1 before vecInt[i] to left
sort(vecInt.begin(),vecInt.begin() + i, compare);
//after step 1 and 2, a new combination is exist
printResult(vecInt, t);
//try do step 1 and 2 from front
i = -1;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
const int N = 5;
int t[N] = {1, 2, 3, 4, 5};
combination(t, 2, N);
system("pause");
return 0;
}
3.如何求所有的組合呢？
如果你理解了上面的東西，我們再來思考一個簡單的問題，如何求1,2,3 的所有組合結果：
別害怕，這個問題比上面的還要簡單，也是二進制的思想，我們用一個3位的二進制來表示一個結果，剛好是從0~7
{} 000
1 001
2 010
1,2 011
3 100
2,3 110
1,2,3 111
代碼如下(位運算不懂的話，看這篇文章《來談談C++ 位運算 & | << >> ^ ~ %》)：http://www.linuxidc.com/Linux/2014-03/98362.htm
// MyCombination.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printEachResult(int t[], int index, int total){
for(int i = 0; i < total; ++i){
if((index>>i)&1 == 1){
cout << t[i] << " ";
}
}
cout << endl;
}
void combination(int t[],int count){
for(int i = 0; i < (1<<count); ++i){
printEachResult(t, i, count);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
const int N = 3;
int t[N] = {1, 2, 3};
combination(t,N);
system("pause");
return 0;
}
