1、求1~N的全排列
(1)我们先从最简单的例子看起：1,2 两个数的情况，显然有1--2, 2--1，两种排列，即1和2交换一下。
1,2,3 三个数的情况：
1--2--3
1--3--2 //固定第一个数，递归的求后两个数的组合，2和3交换一下
2--1--3 //1,2 交换
2--3--1 //固定2， 递归求两个数的组合，交换1,3
3--2--1 //1和3交换
3--1--2 //固定3， 递归求两个数的组合，交换2,1
将上述过程转换为代码：
View Code
void permutation(T* array, int n)
{
permutation(array, n, array, n);
}
template<class T>
void permutation(T* array, int size, T* start, int n)
{
if(n == 1)
{
cout<<array[0]; //output current array;
for(int i = 1; i < size; ++i)
cout<<" "<<array[i];
cout<<endl;
return;
}
permutation(array, size, start + 1, n - 1);//first permutation, 1--2--3
T tmp = start[0];
for(int i = 1; i < n; ++i)
{
//interchange a[0] and a[i]
start[0] = start[i]; //1-2-3 ==> 2-1-3
start[i] = tmp;
permutation(array, size, start+1, n - 1);
start[i] = start[0]; //note to copy the original order back, 2-1-3 ==> 1-2-3, next round interchange 1 and 3
start[0] = tmp;
}
其实想清楚了很简单， 就是递归的思想，2个数很好想：做一下交换，延伸到3个数、到N个数。
3个数1-2-3，可以1和2、3分别做一次交换，后边又成了两个数的情况。 Aha, world is simple!
(2) 在c++的标准库里，有next_permutation(array, array+N)这种东西，可以拿过来直接用：
View Code
#include<algorithm>
using namespace std;
template<class T>
void permutation(T* array, int n);
template<class T>
void combination(T* array, int N, int m);
int main()
{
int array[] = {1,2,3};
permutation(array, 3);
cout<<"-----------"<<endl;
do
{
for(int i = 0; i < 3; ++i)
cout<<array[i]<<ends;
cout<<endl;
}while( next_permutation(array, array+3) );
system("pause");
return 0;
运行结果如下图所示。
在写这个simple的算法过程中， 看到了两篇不错的博客，一并转载过来：
http://apps.hi.baidu.com/share/detail/19561533
http://www.cppblog.com/yindf/archive/2010/02/24/108312.html
第二篇写的非常好，
了解C++的童鞋都知道algorithm里面有个next_permutation可以求下一个排列数，通过《STL 源码剖析》（或者自己读代码）可以知道其实现，比如：
abcd next_permutation -> abdc
那么，为什么abcd的下一个是abdc而不是acbd呢？
说简单一点，用 1，2，3，4 代替 a，b，c，d，可以得到：
//注释一下：这里的所谓的中间转换，其实就是逆序数...
原排列 中间转换 值
1，2，3，4 3，2，1 ((3 * (3) + 2) * (2) + 1) * (1) = 23
1，2，4，3 3，2，0 ((3 * (3) + 2) * (2) + 0) * (1) = 22
1，3，2，4 3，1，1 ((3 * (3) + 1) * (2) + 1) * (1) = 21
1，3，4，2 3，1，0 ((3 * (3) + 1) * (2) + 0) * (1) = 20
1，4，3，2 3，0，1 ((3 * (3) + 0) * (2) + 1) * (1) = 19
. . .
. . .
. . .
4，3，2，1 0，0，0 ((0 * (3) + 0) * (2) + 0) * (1) = 0
| | | | | |
| | | |
| |
上面的中间转换指的是：每一个数字后面比当前位数字大的数字的个数。比如：
1，3，4，2 中，1 后面有(3, 4, 2) 他们都大于1，所以第一位是 3
3 后面有(4, 2), 但只有4大于3，所以第二位是 1
4 后面有(2), 没有比4 大的，所以第三位是 0
最后一位后面肯定没有更大的，所以省略了一个0。
经过这种转换以后，就得到了一种表示方式（中间转换），这种表达方式和原排列一一对应，可以相互转化。
仔细观察这种中间表达方式，发现它的第一位只能是（0，1，2，3），第二位只能是（0，1，2），第三位只能是（0，1）。
通常，数字是用十进制表示的，计算机中用二进制，但是现在，我用一种特殊的进制来表示数：
第一位用1进制，第二位用2进制。。。
于是就得到了这种中间表示方式的十进制值。如：
阶
| | |
1，1，0 ----> ((1 * (3) + 1) * (2) + 0) * (1) = 8
3，1，0 ----> ((3 * (3) + 1) * (2) + 0) * (1) = 20
这样，就可以得到一个十进制数和一个排列之间的一一对应的关系。
现在排列数和有序的十进制数有了一一对应的关系（通过改变对应关系，可以使十进制数升序）。
-------------------------------------------------------
1，2，4，3 3，2，0 ((3 * (3) + 2) * (2) + 0) * (1) = 22
1，3，2，4 3，1，1 ((3 * (3) + 1) * (2) + 1) * (1) = 21
看完了这儿我就在想，为什么最后一位表示1进制，依次是2进制、3进制，为什么这样表示出来之后正好就是 [0,4!)，why?
很容易理解，因为最高位*(3)表示，其可能出现的最大的逆序数=3。
其实就是排列的选择过程，C(4,1)*C(3,1)*C(2,1)*C(1,1)
2、求1~N个数选m个所有的组合
我们同样从最简单的例子开始入手，1-2-3，选2个数
先考虑1-2中选1个数的情况C(2,1)： 1, 2， 第一次选1， 选定了1之后，下一次从1之后开始选，选2，即保证一个选择的顺序
1-2-3，从中选2个数 C(3,2)：
1 -- ? 选定第一个数，下面成了C(2,1)
1--2, 1--3 两种。
我们保证按顺序去选， 因为是C(3,2)，所以第1个数可以取到：1, 2， 1已经选过，下一轮选2
2 -- ?， 选定第一个数=2，下面又成了C(2,1)，但是要按顺序选：从3一个数里 C(2,1)
2--3，只有这一种情况。
trick就在于为了避免重复，我们以“有序”的方式去选择数 1--2, 1--3, 2--3
我们将上边的过程先转换为伪码：
//C(N, m)
if(m < 1)
//输出结果 a[1~m]
else
{
for(i = m ~ N) // 为了方便，代码逆着选，第m个数 可以依次取[m, N]
{
a[m] = i; //填第m个数
C( i - 1, m - 1); // i 已经被 a[m]选过了，下一轮只能从i - 1开始选。
}
}
源代码：
View Code
#include<algorithm>
using namespace std;
template<class T>
void combination(T* array, int N, int m);
int main()
{
int array[] = {1,2,3,4,5};
combination(array, 5, 3);
system("pause");
return 0;
}
template<class T>
void combination(T* array, int N, int m)
{
T* result = new T[m + 1];
result[0] = m; //result[0]记录元素的个数
combination(array, result, N, m);
delete []result;
}
template<class T>
void combination(T* array, T* result, int N, int m)
{
if(m < 1)
{
//output a[ 0 ~ m-1 ];
for(int i = 1; i <= result[0]; ++i)
cout<<result[i]<<ends;
cout<<endl;
return;
}
for(int i = N - 1; i >= m - 1; --i) //第m个数，可以从array[m-1] 取到 array[N-1];
{
result[m] = array[i];
combination(array, result, i, m - 1); //注意这里是 i, 从前i个元素再选m - 1个;
}
3、求1~N所有的幂集(即所有的子集)
当然可以按2依次求C(N,1), C(N,2)...C(N,N)
但是有更快的算法，就是迭代 1~2^N所有的整数，统计每个整数中含有的1的个数(二进制中)
二进制位取1表示取该元素，取0表示不取该元素。
-------------------------------------------------
跑题：
把一个问题映射到二进制数，有很多好玩儿的题目：
有1000瓶老鼠药和10只老鼠，其中有一瓶老鼠药是有毒的，老鼠喝了有毒的老鼠药2天就会挂掉，如何在两天之内找到哪瓶老鼠药是有毒的？
(tips：老鼠列成一排，每只老鼠看成一个bit位，1~1000给对应bit位是1的老鼠喝，最后挂掉的老鼠是 药瓶编号的 bit位1(其它是0)，该瓶老鼠药是有毒的)
原文链接: https://www.cnblogs.com/worldisimple/archive/2012/04/24/2468743.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/48427
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
