我們知道，一個(gè)集合的子集通常可由一個(gè)位串來表示，比如對于集合 {a, b, c, d, e}，可用位串 s = ”11001” 來表示其子集 {a, b, e}。當(dāng)集合的大小不大于機(jī)器的字長（在下文中將假設(shè)字長為32）時(shí)，這些位串又可用一個(gè)無符號整數(shù)來表示，比如上面的 s 可以存儲為 0b10011 = 19。在此種情形下，很多集合操作都可以通過位運(yùn)算來完成，一些常見操作如下：

求集合 A, B 的交集: a & b

求集合 A, B 的并集: a | b

求集合 A 的補(bǔ)集：~a

求集合 A – B：a & (~b)

測試集合 A 是否包含第 i 個(gè)元素：(a & (1<<i)) != 0

測試集合 A 是否是集合 B 的父集：(a & b) == b

當(dāng)然，這些操作還有很多，比如求對稱差就是一個(gè)異或等等，這里就不一一列舉了，因?yàn)檫@并不是本文的重點(diǎn)。本文的主要目的是討論一些集合上的組合搜索。具體來說就是怎樣高效遍歷一個(gè)集合的所有子集（subset），或者一個(gè)集合的含有固定元素個(gè)數(shù)的所有子集（亦即是組合，combination）。如果你對怎么實(shí)現(xiàn)這些操作不感興趣，你可以直接下載本文所附的代碼，里面包含了已經(jīng)封裝好了的類，和一些簡單的例子。如果你感興趣，而且正巧知道一點(diǎn)常用位運(yùn)算技巧的話，請 continue。

1. 遍歷所有子集

1.1 遍歷全集的所有子集

若全集 U 有 n 個(gè)元素，表示成位串為 1111…1（n個(gè)1），對應(yīng)的無符號整數(shù)即是 2^n – 1 = (1 << n) - 1（注意當(dāng) n 等于32 時(shí)需要做一些調(diào)整，不過我想你也大概不會要遍歷到這么大一個(gè)集合的所有子集）。容易觀察到，U 的所有子集剛好與區(qū)間 [0, 2^n – 1] 內(nèi)的所有整數(shù)形成一一映射，于是通過下面這段代碼即可依次訪問 U 的所有子集：

這是每個(gè)程序員都應(yīng)該知道的技巧。舉個(gè)例子，若全集為 {a, b, c}，那么上面這段代碼所訪問的子集及順序?qū)⑷缦卤硭荆?/p>

序號	值	位串	子集
1	0b000	000	Φ
2	0b001	100	{a}
3	0b010	010	{b}
4	0b011	110	{a, b}
5	0b100	001	{c}
6	0b101	101	{a, c}
7	0b110	011	{b, c}
8	0b111	111	{a, b, c}

注意這里訪問子集的順序并不是 lexicographic order (lex)，而是另外一種與 lex  關(guān)系微妙的序，被稱為 colexicographic order (colex)。lex 是從左到右依次比較，而 colex 正好相反，實(shí)際上在 colex 中，如果將各子集反轉(zhuǎn)一下，比如將集合 {a, b, c} 寫成 {c, b, a}，你會發(fā)現(xiàn)，反轉(zhuǎn)之后的子集們正是按照 lex 排列的。在下表中列出了 {a, b, c} 的所有子集的 lex 序及 colex 序，為了看起來更方便，省略了集合符號，注意觀察 lex 與 colex 之間的聯(lián)系。

再說說如何反向的遍歷所有子集。這個(gè)其實(shí)很顯然，因?yàn)?++i 的逆操作是 --i ，因此對上面的代碼做點(diǎn)小修改即得到 reverse colex：

1.2 遍歷子集的所有子集

有些時(shí)候我們不僅需要遍歷全集的所有子集，還需要遍歷某個(gè)子集的所有子集。你可能會想這似乎沒什么區(qū)別啊，因?yàn)楫?dāng)針對某個(gè)子集來討論其所有子集時(shí)，這個(gè)子集也就成了全集。的確，在數(shù)學(xué)上當(dāng)我們要考慮某個(gè)集合的冪集時(shí)，并不需要區(qū)別這個(gè)集合是全集還是全集的某個(gè)子集。但是當(dāng)集合是用位串來表示時(shí)，情況就發(fā)生變化了，因?yàn)檎且粋€(gè)約定的全集決定了位串的長度，同時(shí)也決定了位串中的每個(gè)位與全集中的哪個(gè)元素相對應(yīng)，換句話說就是定義了位串與子集之間的映射關(guān)系。如果想將某個(gè)子集做為全集來處理，你就必須重新進(jìn)行映射。舉個(gè)例子，若全集為 U = {a, b, c, d, e}，若想得到它的一個(gè)子集 S = {a, e} 的所有子集，可以暫時(shí)先將 S 做為一個(gè)全集來處理，按照上面遍歷全集的算法將依次得到位串 00, 10, 01, 11，這些位串的第1位代表元素 a，第2位代表元素 e。當(dāng)再回到全集 U 上時(shí)，由于 U 上的位串是第1位代表 a，第5位代表 e，因此還需要進(jìn)行一個(gè)映射將 S 上的位串映射為 U 上的位串。下表按照 colex 依次列出了 S 的所有子集，注意從 S 到 U 的映射關(guān)系。

一個(gè)映射操作可以重新敘述如下：給定一個(gè) n 位的二進(jìn)制數(shù) u，一個(gè) m  位的二進(jìn)制數(shù) v，且有在 u 中1的個(gè)數(shù)等于 m 。設(shè)在 u 中為1的位的索引從低到高依次為 p1,p2,…,pm，再設(shè)下標(biāo)操作符 [] 可以索引一個(gè)二進(jìn)制數(shù)的某個(gè)位（最低位的索引為1），那么映射操作將返回一個(gè) n 位二進(jìn)制數(shù) w，滿足

對所有 1 <= i <= n ，若u[i] = 0，則 w[i] = 0

對所有 1 <= i <= m ，w[pi] = v[i]

比如給定 u = 0b10110100, v = 0b1100, 將得到 w = 0b10100000。這個(gè)映射操作是 non-trival 的，也就是說你不能指望通過簡單的一兩次位運(yùn)算就能得償所愿。具體怎么實(shí)現(xiàn)咱們后面再講，因?yàn)樵谶@里使用一個(gè)非常漂亮的技巧可以繞過這個(gè)操作。為了敘述方便，先定義一個(gè)概念（非正式）：

片段：對于任意兩個(gè) n 位二進(jìn)制數(shù) x 和 mask，若在 mask 中為1的位的索引分別為 p1,p2,…,pk，那么將這些位 x[p1],x[p2],…,x[pk] 稱為 x 在 mask 上的片段，不妨記為 [x@mask]。比如對于 x = 0b0001, mask = 0b1001, 那么 [x@mask] 由 x 的第1位和第4位組成，用紅色標(biāo)識出來即為 0b0001。

在前面我們已經(jīng)看到，遍歷子集的關(guān)鍵就是一個(gè)+1（colex）或者-1（reverse colex）操作。如果我們能在片段上直接進(jìn)行+1或者-1操作，那就解決問題了。比如 0b0001 + 1 直接就得到 0b1000。事實(shí)上，這的確可以做到，而且非常簡單。

先來看看片段上的-1操作（因?yàn)?1比+1簡單，而且也有更多的人知道這一技巧）。若 x & mask = x，即 x 是 mask 的子集，則有：

[x@mask] - 1 = (x – 1) & mask

上面這個(gè)公式為什么是正確的？因?yàn)榧热?x 是 mask 的子集，因此 mask 為0的位在 x 中也為0。這些0在-1運(yùn)算中會正確的傳播借位，就如同它們并不存在一樣。比如 0b1000 – 1 = 0b0111（注意在第1位中產(chǎn)生的借位是如何傳播到第4位的）。最后再與 mask 相與，清零掉那些無關(guān)的位，即得到正確的結(jié)果 0b0001。

于是，如果想要按照 reverse colex 遍歷某個(gè)子集（假設(shè)表示成一個(gè)無符號整數(shù)為 s) 的所有子集，將 s 做為 mask 然后進(jìn)行-1操作即可，代碼如下：

再來看看如何在片段上進(jìn)行+1操作。受上面-1操作的啟發(fā)，我們意識到這里最關(guān)鍵的問題在于如何正確的傳播進(jìn)位。傳播借位是將無關(guān)位設(shè)為0，那傳播進(jìn)位呢？——將無關(guān)位設(shè)為1，Bingo!。怎么將無關(guān)位設(shè)為1呢，將mask取反，然后再相或就成，于是有：

[x@mask] + 1

    = ((x | (~mask)) + 1) & mask

    = (x + (~mask) + 1) & mask     // 若 x & mask = x，那么 x | (~mask) = x + (~mask)

    = (x – mask) & mask                // (~mask) + 1 = – mask

現(xiàn)在我們終于可以正向地遍歷子集 s 的所有子集了：