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.在计算机中如何高效的实现排列算法？
乍一看，这个问题并不简单。有递归的实现方式，效率较低，还比较难，先不考虑。我们注意到一种以二进制的思想的实现方式，比较高效，来讲讲它。
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
#include
#include
using namespace std;
void printResult(vector& 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 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
// MyCombination.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#include
#include
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< 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;
}