<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Combination - 組合 -------- #### 問題 從擁有$$ n $$個元素的集合$$ A = \{a_0, a_1, a_2, \dots ,a_{n-1} \} $$中任意取$$ m $$個元素（$$ m \leq n $$，$$ m $$和$$ n $$都是自然數），求所有組合。 #### 解法 本文末尾列了很多關于組合算法的文獻。本文介紹一種簡單易記的算法。 設置數組\(s = [s_0,s_1,s_2, \dots ,s_{n-1}]\)表示對集合\(A\)的選擇，第\(i\)個數字\(s_i = 1\)表示選擇數字\(a_i\)，\(s_i = 0\)表示不選擇數字\(a_i\)。假設初始狀態下從集合\(A = \{a_0,a_1,a_2, \dots ,a_{n-1} \}\)中取出\(0\)個元素組成組合，即\(s = [0_0,0_1,0_2, \dots ,0_{n-1}]\)，得到\(1\)個組合\(\{\}\)。</p> $$ (1) $$從集合$$ A = \{a_0,a_1,a_2, \dots ,a_{n-1} \} $$中取出$$ 1 $$個元素作為組合。則數組$$ s $$中只有一個元素為$$ 1 $$，其他全是$$ 0 $$，唯一的$$ 1 $$在數組$$ s $$中可以選擇任意位置，得到$$ C_1^n = n $$個組合： \[ \begin{array}{lcr} [1_0,0_1,0_2, \dots ,0_{n-1}] && (1-1) \\ [0_0,1_1,0_2, \dots ,0_{n-1}] && (1-2) \\ [0_0,0_1,1_2, \dots ,0_{n-1}] && (1-3) \\ & \cdots & \\ [0_0,0_1,0_2, \dots ,1_{n-1}] && (1-n) \end{array} \] <p id="i">\((2)\)從集合A中取出2個元素作為組合，可以看作是在第1輪操作數組s后得到的n個組合的基礎上增加一個1。 </p> <p id="i">對于第\(1\)輪中的數組\((1-1)\quad [1_0,0_1,0_2, \dots ,0_{n-1}]\)增加一個\(1\)后得到數組\([1_0,1_1,0_2, \dots ,0_{n-1}]\)。原本的\(1_0\)保持不變，新增的\(1_1\)可以選擇后面等于\(0\)的\(n-1\)個位置，生成\(n-1\)個組合： </p> \[ \begin{array}{lcr} [1_0,1_1,0_2,0_3, \dots ,0_{n-1}] && (2-1-1) \\ [1_0,0_1,1_2,0_3, \dots ,0_{n-1}] && (2-1-2) \\ [1_0,0_1,0_2,1_3, \dots ,0_{n-1}] && (2-1-3) \\ & \cdots & \\ [1_0,0_1,0_2,0_3, \dots ,1_{n-1}] && (2-1-(n-1)) \end{array} \] <p id="i">需要注意的是，新增的\(1\)必須在原數組中所有的\(1\)的后面。對于數組\((1-2) \quad [0_0,1_1,0_2, \dots ,0_{n-1}]\)，新增的\(1\)只能選擇后面等于\(0\)的\(n-1\)個位置，生成\(n-2\)個組合： </p> \[ \begin{array}{lcr} [0_0,1_1,1_2,0_3, \dots ,0_{n-1}] && (2-2-1) \\ [0_0,1_1,0_2,1_3, \dots ,0_{n-1}] && (2-2-2) \\ & \cdots & \\ [0_0,1_1,0_2,0_3, \dots ,1_{n-1}] && (2-2-(n-2)) \end{array} \] <p id="i">如果不注意，讓新增的\(1\)在原數組的任意的\(1\)的前面，則會產生重復的組合，仍然以數組\((1-2) \quad [0_0,1_1,0_2, \dots ,0_{n-1}]\)為例，如果新增的\(1\)可以選擇任意等于\(0\)的位置，會生成\(n-1\)個組合： </p> \[ \begin{array}{lcr} [1_0,1_1,0_2,0_3, \dots ,0_{n-1}] && (2-2-0) \\ [0_0,1_1,1_2,0_3, \dots ,0_{n-1}] && (2-2-1) \\ [0_0,1_1,0_2,1_3, \dots ,0_{n-1}] && (2-2-2) \\ & \cdots & \\ [0_0,1_1,0_2,0_3, \dots ,1_{n-1}] && (2-2-(n-2)) \end{array} \] <p id="i">但其中\((2-2-0) \quad [1_0,1_1,0_2,0_3, \dots ,0_{n-1}]\)與第\(1\)個數組產生的組合重復了。對第\(1\)輪中所有的數組重復該操作，即可得到選取\(2\)個元素的所有組合，共有\(C_2^n = \frac{n \times (n-1)}{2} \)個。 </p> <p id="i">\((3)\)從集合\(A\)中取出\(3\)個元素作為組合，可以看作是在第\((2)\)輪操作的\((n-1)!\)個組合基礎上增加一個\(1\)，對于之前的每個組合，保持之前兩個\(1\)不變，新的\(1\)可以選擇原數組中最后一個\(1\)之后的任意等于\(0\)的位置。注意新增的\(1\)不能比原數組中的任意的\(1\)更靠前，必須在所有的\(1\)之后的位置進行選擇。 </p> <p id="i">重復上述的操作，直到選取\(m\)個元素，即可得到所有的組合，算法結束。然后根據\(s\)的全排列生成集合\(A\)的所有組合即可。該算法時間復雜度為\(C_m^n = \frac{n!}{m! \cdot (n-m)!} \)。 </p> </div> <br> StackOverflow上關于組合產生算法的問題： * [http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n](http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n) 二項式系數： * [https://en.wikipedia.org/wiki/Binomial_coefficient](https://en.wikipedia.org/wiki/Binomial_coefficient) Chase’s Twiddle - Algorithm 382: Combinations of M out of N Objects: * [http://dl.acm.org/citation.cfm?id=362502](http://dl.acm.org/citation.cfm?id=362502) * [http://www.netlib.no/netlib/toms/382](http://www.netlib.no/netlib/toms/382) Buckles - Algorithm 515: Generation of a Vector from the Lexicographical Index: * [http://dl.acm.org/citation.cfm?id=355739](http://dl.acm.org/citation.cfm?id=355739) * [https://www.researchgate.net/profile/Bill_Buckles/publication/220492658_Algorithm_515_Generation_of_a_Vector_from_the_Lexicographical_Index_G6/links/5716d7ad08ae497c1a5706ec.pdf](https://www.researchgate.net/profile/Bill_Buckles/publication/220492658_Algorithm_515_Generation_of_a_Vector_from_the_Lexicographical_Index_G6/links/5716d7ad08ae497c1a5706ec.pdf) Remark on algorithm 515: Generation of a vector from the lexicographical index combinations: * [http://dl.acm.org/citation.cfm?id=1236470](http://dl.acm.org/citation.cfm?id=1236470) -------- #### 源碼 [import, lang:"c_cpp"](../../../src/CombinatorialMathematics/Combination.hpp) #### 測試 [import, lang:"c_cpp"](../../../src/CombinatorialMathematics/Combination.cpp)