全排列算法解析.doc

全排列以及相关算法在程序设计过程中，我们往往要对一个序列进行全排列或者对每一个排列进行分析。全排列算法便是用于产生全排列或者逐个构造全排列的方法。当然，全排列算法不仅仅止于全排列，对于普通的排列，或者组合的问题，也可以解决。本文主要通过对全排列以及相关算法的介绍和讲解、分析，让读者更好地了解这一方面的知识，主要涉及到的语言是C和C+。本文的节数：1. 全排列的定义和公式：2.时间复杂度：3.列出全排列的初始思想：4.从第m个元素到第n个元素的全排列的算法：5.全排列算法：6.全排列的字典序：7.求下一个字典序排列算法：8.C+ STL库中的next_permutation()函数：（#include）9.字典序的中介数，由中介数求序号：10. 由中介数求排列：11. 递增进位制数法：12. 递减进位制数法：13. 邻位对换法：14. 邻位对换法全排列：15. 邻位对换法的下一个排列：16. 邻位对换法的中介数：17.组合数的字典序与生成：由于本文的，内容比较多，所以希望读者根据自己的要求阅读，不要一次性读完，有些章节可以分开读。第1节到第5节提供了全排列的概念和一个初始的算法。第6节到第8节主要讲述了字典序的全排列算法。第9到第10节讲了有关字典序中中介数的概念。第11到第12节主要介绍了不同的中介数方法，仅供扩展用。第13节到15节介绍了邻位对换法的全排的有关知识。16节讲了有关邻位对换法的中介数，仅供参考。第17节讲了组合数生成的算法。1.全排列的定义和公式：从n个数中选取m（m=n）个数按照一定的顺序进行排成一个列，叫作从n个元素中取m个元素的一个排列。由排列的定义，显然不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数，称为排列数。从n个元素取出n个元素的一个排列，称为一个全排列。全排列的排列数公式为n!，通过乘法原理可以得到。2.时间复杂度：n个数（字符、对象）的全排列一共有n!种，所以全排列算法至少时O(n!)的。如果要对全排列进行输出，那么输出的时间要O(n*n!)，因为每一个排列都有n个数据。所以实际上，全排列算法对大型的数据是无法处理的，而一般情况下也不会要求我们去遍历一个大型数据的全排列。3.列出全排列的初始思想：解决一个算法问题，我比较习惯于从基本的想法做起，我们先回顾一下我们自己是如何写一组数的全排列的：1，3，5，9（为了方便，下面我都用数进行全排列而不是字符）。1，3，5，9.（第一个）首先保持第一个不变，对3，5，9进行全排列。同样地，我们先保持3不变，对5，9进行全排列。保持5不变，对9对进行全排列，由于9只有一个，它的排列只有一种：9。接下来5不能以5打头了，5，9相互交换，得到1，3，9，5.此时5，9的情况都写完了，不能以3打头了，得到1，5，3，91，5，9，31，9，3，51，9，5，3这样，我们就得到了1开头的所有排列，这是我们一般的排列数生成的过程。再接着是以3、5、9打头，得到全排列。这里还要注意的一点是，对于我们人而言，我们脑子里相当于是储存了一张表示原有数组的表，1，3，5，9，1开头的所有排列完成后，我们选择3开头，3选完了之后，我们选择5开头，而不会再返过来选1，而且知道选到9之后结束，但对于计算机而言，我们得到了3，5，1，9后，可能再次跳到1当中，因为原来数组的顺序它已经不知道了，这样便产生了错误。对于算法的设计，我们也可以维护这样一个数组，它保存了原始的数据，这是一种方法。同时我们还可以再每次交换后再交换回来，变回原来的数组，这样程序在遍历的时候便不会出错。读者可以练习一下这个过程，思考一下你是如何进行全排列的，当然，你的方法可能和我的不太一样。我们把上面全排列的方法归纳一下，基本上就是：任意选一个数（一般从小到大或者从左到右）打头，对后面的n-1个数进行全排列。聪明的读者应该已经发现，这是一个递归的方法，因为要得到n-1个数的全排列，我们又要先去得到n-2个数的全排列，而出口是只有1个数的全排列，因为它只有1种，为它的本身。写成比较规范的流程：1. 开始for循环。2. 改变第一个元素为原始数组的第一个元素（什么都没做）。3. 求第2个元素到第n个元素的全排列。4. 要求第2个元素到第n个元素的全排列，要递归的求第3个元素到第n个元素的全排列。.5.直到递归到第n个元素到第n元素的全排列，递归出口。6.将改变的数组变回。7.改变第一个元素为原始数组的第二个元素。（注：理论上来说第二次排列时才改变了第一个元素，即第6步应该此时才开始执行，但由于多执行一次无义的交换影响不大，而这样使得算法没有特殊情况，更容易读懂，如果一定要省时间可以把这步写在此处，这种算法我在下文中便不给出了，读者可以自己写。）5. 求第2个元素到第n个元素的全排列。6. 要求第2个元素到第n个元素的全排列，要递归的求第3个元素到第n个元素的全排列。.5.直到递归到第n个元素到第n元素的全排列，递归出口。6.将改变的数组变回。.8.不断地改变第一个元素，直至n次使for循环中止。为了实现上述过程，我们要先得到从第m个元素到第n个元素的排列的算法：4.从第m个元素到第n个元素的全排列的算法：void Permutation(int A, int m, int n)if(m = = n)Print(A); /直接输出，因为前n-1个数已经确定，递归到只有1个数。return;elsefor(i=m;in;i+) /进入for循环，对应第一步swap(am,ai); /交换，对应第二步Permutation(A,m+1,n); /递归调用，对应三至五步swap(am,ai); /交换，对应第六步为了使代码运行更快，Print函数和swap函数直接写成表达式而不是函数（如果是C+的话建议把swap写成内联函数，把Print写成宏）void Permutation(int A, int m, int n)int i, int temp;if(m = = n)for(i = 0;in;i+)if(i != n-1)printf(%d ,Ai); /有加空格elseprintf(%d Ai); /没加空格 /直接输出，因为前n-1个数已经确定，递归到只有1个数。printf(n);return;elsefor(i=m;i b(k+1),则称排列c位于排列b（关于字典序）的后面。如1，2，3，4的字典序排在1，2，4，3的前面（k=2），1，3，2，4的字典序在1，2，3，4(k=1)的后面。下面列出1，2，3按字典序的排列结果：1，2，31，3，22，1，32，3，13，1，23，2，1（有些读者会发现它们手写排列的时候也不自觉得遵照着这个规则以妨漏写，对于计算机也一样，如果有这样习惯的读者的话，那它们的实际算法更适合于表达为下面要讲的算法。）定义字典序的好处在于，排列变得有序了，而我们前面的递归算法的排列是无序的，由同一个序列生成的不同数组（排列）如1,2,3,4和2,3,4,1的输出结果的顺序是不同的，这样便没有统一性，而字典序则可以解决这个问题。很明显地，对于一个元素各不相同的元素集合，它的每个排列的字典序位置都不相同，有先有后。接下来讲讲如何求某一个排列的紧邻着的后一个字典序。对证明不感兴趣的读者只要读下面加色的字即可。定理：我们先来构造这样一个在它后面的字典序，再证明这是紧邻它的字典序。对于一个排列a1,a2,a3.an,如果a(n) a(n-1)，那么a1,a2,a3.a(n),a(n-1)是它后面的字典序，否则，也就是a(n-1) a(n),此时如果a(n-2) a(m)【如果a(n) a(2) .a(n)，是最大的字典序】，显然后面的序列满足a(m+1)a(m+2).a(n).找到a(m+1)到a(n)中比a(m)大的最小的数，和a(m)交换，并把交换后的a(m+1)到a(n)按照从小到大排序，前m-1项保持不变，得到的显然也是原排列后面的字典序，这个字典序便是紧挨着排列的后一个字典序。下面证明它是紧挨着的。1.如果还存在前m-1项和原排列相同并且也在原排列后面的字典序a1,a2,a3.bm,.，bm原am，假设它在我们构造的字典序前面，那么必有bm 交换后的am，但这是不可能的，因为am是后面序列中大于原来am的最小的一个，而bm必然又是后面序列中的大于am的一个元素，产生了矛盾。2.如果还存在前前m项和原排列相同并且也在原排列后面的字典序，它不可能在我们构造的字典序前面，因为我们对后面的数进行了升序排列，不存在比a(m+1)还小的数。3.如果还存在前k项（ka(k+1)k+1 = 0;i-)if(Ai+1 Ai)break;if(i 0)return false;m = i;i+;for(;in;i+)if(Ai 、有没有=号都是确定的，不能改，否则出现处理相同元素时便会陷入死循环，具体的写法读者可以自己举例判断，看看怎样会进入死循环。如果要使之前递归的算法不重复，在交换之前要判断相邻着的两个数是否相同，如果相同，则不交换，比如和Ai交换，要判断Ai是否等于Ai+1）。不过这个算法的缺陷是它把原来数组给改变了，读者可以自行在Next_Permutation当中使用int* Array = new int(sizeof(A);或者int* Array = malloc(sizeof(A),然后把数组拷贝一遍，不对原数组进行处理，那么相应的全排列也要自己改写了，我这里就不写了。8. C+ STL库中的next_permutation()函数：（#include）幸运的是，C+已经给我们提供了next_permutation模版函数，所以不用自己写，也就不用担心死循环的问题，不过这个函数没有输出，而是直接把数组变成了它的下一个字典序。下面给出它的源代码：/ TEMPLATE FUNCTION next_permutationtemplate inlinebool next_permutation(_BI _F, _BI _L)_BI _I = _L; /定义新的迭代器_I并将尾地址赋给它。if (_F = = _L | _F = = -_I) /如果首地址等于尾地址或者等于尾地址小1，直接返回falsereturn (false); /要注意是因为我们传递的是尾地址加1（A+n = An的地址），这个判断主要是考虑边界问题。for (; ; ) /死循环，用于找到a(m+1) a(m)._BI _Ip = _I; /定义迭代器_Ip并将_I赋给它。if (*-_I *_Ip) /这里在比较a(m+1)和a(m)的大小，没找到则到下一个循环。如果/找到，进入条件句，由于是用了-运算符，所以得到的实际上是_Ip，也即a(m)。 _BI _J = _L; /定义新的迭代器_J并将尾地址赋给它，相当于从结尾开始/找。前面我的算法是从a(m+1)开始往后找，理论上从结尾开始找比较好，建议读者写的时/候也从结尾往前找。for (; !(*_I *-_J); ) /循环，直到找到 _I_J，由于是减减，所以得到了第一/个比_I大的元素。由于是从结尾开始找，所以加了！，和我的相反。;/仅仅为了找而找。iter_swap(_I, _J);/a(m)和a(i)交换，相当于我写的swap语句，注意传递的是迭/代器，修改的是值。reverse(_Ip, _L);/相比于我的全排序，直接把a(m+1)到a(n)反序更有效率。return (true); /返回。if (_I = = _F) /判断是否到起点了，相应于m+1 = 2，则把刚才反过来的反回去，/再返回false reverse(_F, _L);/有些读者喜欢在反序之前判断是否到起点，而实际上到起点的情况只有一种（最后一个），/不断地判断很浪费时间，还不如在最后再反回来。return (false); 它的第一个参数是迭代器（指针、数组）的首地址，第二个参数是末地址，可以这样传递：next_permutation(A,A+n)来获得整个数组的下个字典序。我在上面已经写了完整的解释，大家可以对比我的算法和C+标准库里的算法，当然大家可以明显看到标准库算法的优越性，大家可以照着上面的解释自己写一个，不用全一样，模式一样即可，它的算法是最高效的（要不怎么能当模板？）。当然，标准库的算法为了使效率最快，安全性最高，总是喜欢用一些+啊-啊之类的运算符使得代码难读，读者在这方面可以不用模仿，算法上模仿就成了。下面再补充一些：在库中还有一个可以增加比较器的模版函数，不过实际上这个函数也不善于处理大型数据，有兴趣可以用。在C+标准库中还提供了找上一个字典序的算法，perv_permutation()，用法一样，下面我附上原码，就不解释了，原理差不多，有兴趣的读者可以自己读读或者自己写一个。/ TEMPLATE FUNCTION prev_permutationtemplate inlinebool prev_permutation(_BI _F, _BI _L)_BI _I = _L;if (_F = _L | _F = -_I)return (false);for (; ; )_BI _Ip = _I;if (!(*-_I *_Ip)_BI _J = _L;for (; *_I 0 7654321-5039(读者自己算一下)。讲了这么多，读者可能觉得这个方法看着非常麻烦，它到底哪里有利于求原排列呢？下面就讲它确定原排列的方法：数空格法。_ _ _ _ _ _ _我们画这样七个空格，来求342221的原排列：第7位数字是3，我们从右向左数3个空格，再往前数一个空格，空格中填入对应的位数7，把对应的空格擦除。_ _ _ 7 _ _ _。第6位数字是4，我们从右向左数4个空格，其中已经放上数的不算空格，再往前数一个空格，空格中填入6，把对应空格擦除。_ 6 _ 7 _ _ _。接下来的步骤也是一样的，第5位的数字是2，数2个空格，再往前数一个空格填入5。_ 6 _ 7 5 _ _。第4位是2，数2个空格再往前数一个空格填入4。_ 6 4 7 5 _ _。第3位是2，数2个空格再往前数一个空格填入3.3 6 4 7 5 _ _。第2位是1，数1个空格，再往前数一个空格填入2.3 6 4 7 5 2 _。第1位是0，数0个空格，再往前数一个空格填入1.3 6 4 7 5 2 1.由此，我们得到了原来的排列3 6 4 7 5 2 1。可以看到，整个过程都是确定的，不需要进行额外的比较，相比于原来的中介数要简便得多，而且得到中介数的方法也基本类似，虽然它的本质是一个递增进制数可能有些困扰，如果不去管它的本质，则是以下简单的事情：1. 用原排列求新的中介序。2. 用中介序方便得求得原排列，使用空格法。3. 用中介序的一个公式求得新的序号。接着还要讲讲递增中介数的最后一个好处，那便是可以方便得通过序号求回中介数。对于字典序来说，它是由几个阶乘相加得到的，反推回中介数基本上是不可能的（或者说是比较麻烦的），而对于递增进制中介数，这个过程非常的简单。通过上面的公式，我们很容易得到相逆的公式：记序号为m.m = m1*1 + kn; kn是一进制，恒为0.m1 = m2 * 2 + kn-1; 由进制的关系知道kn-1是二进制的0=kn-1=1m2 = m3 * 3 + kn-2; 由进制的关系知道kn-1是三进制的0=kn-1=2.m(n-2) = m(n-1) * (n-1)+k2; 0=k2=n-2;m(n-1) = k1;得到序号后，除以2取余得到kn-1,商接着除以3取余得kn-2，以此类推得到原中介数。由于递增进位制数法可以在原排列、中介数、序号之间进行较为方便的转换，我们可以从0开始递增中介数，进而转换为原排列并不断地求下一个序列，也可以得到全排列的算法。不过这里我就不写了，读者有兴趣可以写写。12.递减进位制数法：考虑到递增进制法中由于最低位是二进制，而且低位的进制都比较低，在求下一个排列时，中介数加1往往会导致很多的进位，计算比较麻烦，所以有了递减进位，实际上就是将递增进位制的中介数倒过来即可。如342221变成122243.求序号时的公式记住也是倒过来。(k1*3) + k2)*4+k3)*5.kn-2*n + kn-1，其中ki就是递减进制中介数，i从1开始表示从左往右数，即数组的序号（对应n -i + 1位）。这里的n表示的是原排列的元素个数。如122243表示为（1*3+2）*4+2）*5+2）*6+4）*7+3 = 4735.由于低位都是比较高的进制，所以不容易产生进位，求下一个排列非常地简单。我们看这个例子：122243 + 1 = 122244.这里我们不需要再进位，而是很方便的计算。122244对应的序号是4736.反过来求出原排列的方法也很简单，先反序得到递增中介数再运算即可。122244 = 442221(反序) = _ _ _ _ _ _ _ = _ _ 7 _ _ _ _ = _ 6 7_ _ _ _ = _ 6 7 _ 5_ _ = _ 6 7 4 5 _ _ = 3 6 7 4 5 2 1.（读者可以自行练习空格法）和原来的122243对应的排列3 6 4 7 5 2 1相对比，发现仅仅是4和7交换了位置。我们可以再看看122244 +1 = 122245 = 542221（反序）= _ _ _ _ _ _ _ = _ 7 _ _ _ _ _ = _ 7 6 _ _ _ _ = _ 7 6 _ 5 _ _ = _ 7 6 4 5 _ _ = 3 7 6 4 5 2 1. 我们可以发现它仅仅是上一个排列的6和7交换了位置。读者可能发现，如果再加两次，就会有进位，此时排列又更替了。所以，实际上，递减进位制数法的排序采用的就是这种两个相邻元素交换的方式，并且是从右往左单向交换（至于它的数学原理这里就不深究了，有兴趣的读者可以研究一下）。通过递减进位制法也可以得到全排列的算法，相比于递增进位制法较简单。13.邻位对换法：我们从递减进制数法从得到启示，递减进制法中的交换是单向的，这导致交换到头是排列会发生更替，如果我们采用双向的交换，便可以不断地交换下去，于是产生了邻位对换法。邻位对换法在找下一个排列的方法上在很多情况下要比字典序算法要快上许多，因为每次的下一个排列只是交换两个相邻的元素，当然缺点是有到左端或者右端时要进行找最大可移动数的弊端，整体上速度和字面序算法差不多。当然，读者可能还没有理解邻位对换法的概念，下面开始讲解。在讲解之前先介绍数学中的两个概念，不过其实在这节里没有用，下面一节才用到。定义1：在一个序列中任意两个元素对如果满足ak am(k m)，则称为正序，否则称为逆序。定义2：如果一个排列中逆序的数目为奇数，则称为奇排列，若为偶数则称为偶排列。初始的时候，我们假设这个序列是一个升序的序列，而且最小元素至少为1，升序的序列总是偶排列，并且我们设定初始所有数的移动（其实就是交换）的方向均从右向左。我们给出可移动的概念：如果一个数沿着它的方向的邻位比它小，则称这个数是可移动的。由这个概念可以知道，1是永远不可移动的，最大的数除非是在两端而且方向指向序列外面，要不一直是可移动的。我们再规定一个性质：如果一个可移动的数发生了移动，那么比它大的所有数的方向都反过来。对于一个排列而言，它的邻位对换法的下一个排列是最大的可移动的数移动后的结果。我们看一个例子：1，2，3，4.很显然，这是一个偶排列，因为它是升序序列。12,13,14,23,24,34,都是正序。为了得到下一个排列，我们取最大的数4，它是最大的可移动数，并把它向左移动：1，2，4，3.实际上是3和4的交换，这便是它的下一个排列。再移动：1，4，2，3.再移动，4，1，2，3.由此我们得到了四个排列，每次都是通过交换相邻元素实现的。当4到头了之后，无法移动了，此时我们找到可移动的最大的数3，并把它向左移动1次，得到4，1，3，2.此时由于4的移动方向已经反过来了，所以最大可移动数为4，把4依次向右移动：1，4，3，21，3，4，21，3，2，4.4到了头，再次无法移动了，此时最大的可移动的数变成了3，把3向左移动一次，得到3，1，2，4.此时4的移动方向再反过来向左，得到3，1，4，2.3，4，1，2.4，3，1，2.此时3也到头了，此时我们找可移动的最大的数，2.得到4，3，2，1.4和3的移动方向再反向右，3，4，2，13，2，4，13，2，1，4.4到头后，由于此时3的移动方向向右，得到2，3，1，4.则4的方向又反，向左移动2，3，4，12，4，3，1. 4，2，3，1.此时3再向右移动，得到4，2，1，3.此时4再向右移动2，4，1，3.2，1，4，3.2，1，3，4.由此，我们从一个升序排列得到了全排列。通过这个例子，读者应该可以大概了解邻位对换法的基本过程了：1. 找到最大可移动数并移动至端点2. 找到现存的最大可移动数移动一次3. 回到原最大可移动数并移动至另一端点4. 找到现存的最大可移动数移动一次.5.找不到最大可移动数，循环结束，遍历结束。由这个过程也可以直接得到一个非递归的算法，首先我们要写一个找到最大可移动数并移动一次的方法：bool Movable(int A,direct,int n) /direct参数用于接收每个元素移动方向的数组。int max = 1;/初始化最大可移动数为1，因为规定1是最小的数，可以自己设定。int pos = -1;/初始化最大可移动数的位置为-1./*下面先找到最大可移动数位置*/for(int i=0;in;i+)if(ai max)continue;if(i ai+1 & directi) | (i 0 & ai ai-1 & ! directi)max = ai;Pos = i;/*下面对它进行移动*/if(pos = = -1)return false;if(ppos)swap(Apos,Apos+1);swap(directpos,directpos+1);/我这里用同样名字了，可以写模版，也可以改函/数名字elseswap(Apos,Apos-1);swap(directpos,directpos-1);/我这里用同样名字了，可以写模版，也可以改函/数名字/*最后调整所有比最大可移动数大的数的方向*/for(int i = 0;i max)directi = !directi;return true;有了这个方法后，便可以进行全排列了。17. 邻位对换法全排列：void Full_Array(int A, int n) bool* direct = new booln; /产生一个记录每个元素移动方向的数组sort(A,A+n); /将原序列变成一个升序for(int i=0;i0;i-)swap(Ai,Ai-1);swap(directi,directi-1); /我这里用同样名字了，可以写模版，也可以改函/数名字Print(A,n);elsefor(int i=0;i n; i+)swap(Ai,Ai+1);swap(directi,directi+1); /我这里用同样名字了，可以写模版，也可以改函/数名字Print(A,n); while(Movable(A,direct,n);delete direct; 15.邻位对换法的下一个排列：为了让读者更容易理解和掌握邻位对换法的基本过程，我先通过一个例子让大家了解如何去得到下一个排列，并接着给出了相应的算法，但是，如果我们得到了一个排列比如：2，3，4，1.我们仅仅知道通过一次邻位交换可以得到它的下一个排列，但是是哪一位的交换呢？首先，我们得找到最大的数的位置。2，3，4，1.中最大的数位于第3个位置。位置是好找的，那方向如何判断呢？我们接着要判断最大的数此时的移动方向。之前给出了奇排列和偶排列的概念，在这里便用的上了。每当我们的最大的数从一端移到另一端时，就要进行最大可移动数的交换，这个过程过后，在不考虑最大数的数列中便会增加一个逆序。而初始的1，2，3的逆序为0，最大的数在移动的过程中不会改变除去最大数后的数列的顺序，所以，不考虑最大数后的数列的逆序为偶数个时（偶排列），最大数在向左移动，逆序为奇数个时（奇排列），最大数向右移动。2，3，4，1中不考虑最大数的序列2，3，1的逆序为1，所以4在向右移动。同样地，如果最大数此时在某一端点，我们可以通过上述性质判断是移动最大数还是找到最大可移动数并进行交换。当然这里我们还有问题没有解决：如何判断非最大数的数此时的方向呢？如果无法判断这个，还是无法找到下一个排列。与上面类似地，我们可以得到更一般的结论：一个非最大数的方向由所有比它小的数构成的序列的逆序决定的，如果是偶数个时，向左，奇数个时向右也即的所有的数包括最大数都满足这条规则。2，3，4，1中容易知道此时3是向右的，2是向左的，4是向左的，1是不动的。读者可以自己对1，2，3，4这个全排列的每一个进行练习。 16.邻位对换法的中介数：邻位对换法的中介数也不难求。对于某个排列如2341，从1开始看起（1没有方向，不用算），如果它是向左的，则右边所有比它小的数的个数为中介数的最高位，如果是向右的，则左边所有比它小的数的个数为中介数的最高位，位逐次降低，如2对应k1 = 1，最高位为1，3对应k2 = 1，第三位为1，4是向左的，第二位为k3 = 1.得到111为2341的中介数。对应的序号的求法为(1 * 3 + 1) * 4 + 2 = 17，和递减进位的公式一样，所以通过序号求中介数也是和递减进位、递增进位类似，除以n取余，除以n-1除余，。邻位对换法由中介数求原排列的方法似乎也不是很简单，读者就不用掌握了，这里就概括一下：首先要判断最大数的方向，这个和上面一样，要由其它数构成的序列的奇偶性决定，所以要求其它数构成序列的奇偶性，这个奇偶性通过求序号的公式来得到，由性质原排列中取所有小于等于k的数构成的数列（顺序不变）的奇偶性和对应的序号的奇偶性相同。我举简单的例子：2341的中介数为112.那么231的中介数为11（舍掉低相应位数即可得到相应的中介数），则它的序号为1*3+1 = 4是偶数，所以最高位的方向4的方向向左。以此类推即可。17.组合数的字典序与生成：最后我们讲讲组合数的生成。首先我们看看列出集合的所有子集、要列出一个集合1,2,3,4的所有子集是很容易的，我们可以按照二进制数的顺序，0000，0001，0010，0011，0100，0101，0110，0111.来表示我们要取的元素，其中0表示不取，1表示取，这样就获得了一个顺序。而组合也包含在这个顺序当中。我们看从1,2,3,4中选取两个元素的所有组合：0000 0001 0010 0011 0100 0101 0110 0111 1000 1