1.什么是数学中的组合？和排列不同的是，在组合中取出元素的顺序则不在考虑之中。从个元素中取出个元素，这个元素可能出现的组合数的总数量为：以1,2,3,4,5中选2个数为例，总共的组合为：1,21,31,41,52,32,42,53,43,54,52.在计算机中如何高效的实现排列算法？乍一看，这个问题并不简单。有递归的实现方式，效率较低，还比较难，先不考虑。我们注意到一种以二进制的思想的实现方式，比较高效，来讲讲它。首先还是需要讲下上次的排列算法中比较高效的实现方式（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） -- 52,3 （0,1,1,0,0） -- 61,4 （1,0,0,1,0） -- 92,4 （0,1,0,1,0） -- 103,4 （0,0,1,1,0） -- 121,5 （1,0,0,0,1） -- 172,5 （0,1,0,0,1） -- 183,5 （0,0,1,0,1） -- 204,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{} 0001 0012 0101,2 0113 1002,3 1101,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;
}
易网时代-编程资源站