常數時間生成集合劃分

本文章是Shin-ichiro KAWANO and Shin-ichi NAKANO的論文 constant time generation of set partition的部分翻譯，限于譯者的水準,不保證準确，本文最後的插圖也是來自此論文。

緒論

在實踐中常常需要生成一個包含N個元素的K子集劃分。其中每個子集都是非空子集，而且全集中每個元素都是互相可區分的，但是子集中的元素沒有順序觀念，隻是一個集合。是以我們給全集中每個元素生成一個标号，按任意順序排列元素，然後從1标号到N。是以前述問題可以等價為1-N這些自然數分割為K個子集，下面要描述的算法就是這樣一個漸進意義上的常數時間算法，來生成每一個的符合要求的劃分。之是以說是常數時間，是因為每生成一個劃分需要的時間一般為常數，但是由于有些劃分需要回溯，是以是漸進意義上的常數時間。

記号及表示

一個包含N個不同元素的K劃分定義為P(n,k)，而總的劃分數目是S(n,k)。對于S(n,k)，我們有下面這個公式。

$$S(n,k)=S(n-1,k-1)+S(n-1,k)*k$$

我們可以這樣解釋這個公式，對于第n個元素，如果它單獨為一個子集，則這樣的劃分數為S（n-1,k-1）,如果最後一個元素是跟其他元素在同一個集合中，可以先對剩下的n-1個元素生成k劃分，然後在把目前元素插入到這k個集合的随便一個中，是以得到了上述結果。

把一個符合結果的劃分按照每個子集中最小元素來排序，然後按照順序給這些集合生成1-k标号，表示為\(B_1\)------\(B_k\)，可以看出1這個元素一定在中。

生成這些集合之後，我們在使用一個數組來表示第号元素所在的集合，即。是以對于n=6時，對于（1，2，4），（3，6），（5）這樣的一個劃分我們可以表示為位置數組

112132。而且，對于任意的n和k，位置數組之間都有一些限制條件。

1. 對于\(i=1,a_i=1\) ，恒成立
2. 對于\(i>1\)，\(a_i<MAX(a_1,\cdots,a_{i-1})+1 \)
3. \(k=MAX(a_1,\cdots ,a_n)\)

對于滿足這些條件的數組，我們稱之為K限制的生長序列。

操作及其定義

下面的操作都是作用在K限制的生長序列上的，不再另行說明。

回溯操作

對于任何一個K限制的生長序列，可以分為兩種情況讨論。

第一種情況：目前序列為非遞減序列時。即\(a_1\leq a_2 \leq \cdots \leq a_n\)。

對于這種情況，我們定義一個根序列，這個根序列會在後面一直用到-------11...123...k。

設\(a_j\)是從最右端向左數第一個與根序列不同的數，此時\(a_j=a_{j+1}\), 這個是由于目前序列為非遞減序列。由于非遞減，\(a_j <a_{j+1}\) ,而且當小于号成立的時候，不管 是變大了還是變小了，中間總是會有有一個數就不會出現，這個就違反了生長序列的定義。且\(a_{j-1}=a_j\)或者\(a_{j-1}=a_j -1\) ，此時 ，我們将\(a_j\)減少1。此時1，2，3這三個條件都成立，不違反K限制的生長序列的定義。

第二種情況：目前序列有一個或多個逆序對，即存在，使得\(a_j >a_{j+1}\)。

設b是從右往左數第一個滿足\(a_b >a_{b+1}\)的位置，此時對于這個位置和其後繼交換一下元素。交換之後，第一個條件和最後一個條件一定是滿足的，而且第二個條件也是滿足的。是以交換完成的序列還是K限制的生長序列。

我們把最後生成的序列定義為目前序列的父序列，即\(P(A)\),其中A為目前序列。從這裡可以看出，每個不是根序列的目前序列都有一個唯一的父序列。

此外，我們可以證明任何一個包含N個元素的K劃分所生成的位置數組可以通過前面的兩個操作得到根序列：當位置數組中有逆序對時，可以通過第二種交換操作，最終得到一個沒有逆序對的位置序列，其實可以當作冒泡排序，是以步驟是有限個的。當得到非遞減序列之後，采取第一種操作。因為第二種操作消除逆序對，然後第一種操作将整個位置數組的和減1，并可能引發第二種操作。而一個集合的劃分所得到的位置數組的最小和是跟序列的數組和，而且對于這個和隻有根序列這種排列形式，是以最終會得到根序列。

生成操作

前面的回溯操作證明了任何一個非根序列都有一個唯一的父序列，而且每個符合條件的劃分的位置數組都可以通過回溯操作回到根序列。但是我們的目的是為了生成所有的子序列，于是下文開始讨論如何從父序列生成子序列。

同樣是分類讨論，從上面的回溯操作來得到父序列的響應特征。

第一種情況：子序列與父序列是通過第一種回溯操作聯系起來的。

這時，假設減少的是第x個元素，由于操作前第x個元素等于第x+1個元素，第x-1個元素等于第x個元素或比第x個元素小1。是以操作完成之後父序列（x-1,x）可能成為逆序對，再次對是否有逆序對開始讨論。

1. 目前序列有且隻有一個逆序對（x-1,x）

   此時如果存在y>=x且\(a_y = a_{y+1}\)，那麼不可能從一個子序列回溯到父序列。因為第一個操作完成之後，對于下标大于x的位置數組元素是嚴格按照遞增序排列的。是以如果存在這個y使得\(a_y=a_{y+1}\)，則不可能有可通過第一個回溯操作生成目前序列的子序列。

   如果不存在這個y，且\(a_x +1 =a_{x-1}\)，則可以直接将加上一個1，所得的序列仍然符合K限制的生長序列。如果\(a_x +1 =a_{x-1}\)這個條件不成立，則沒有符合第一種回溯操作的子序列

2. 父序列沒有逆序對

   從右向左找到第一個x，使得\(a_x =a_{x-1}\)。

   如果x不等于N，則此時直接将\(a_x\)加上1就得到了符合條件的子序列。

   如果x等于N，這時不存在可以通過第一個回溯操作生成目前序列的子序列。因為根據第一個操作的條件，子序列的最後一個元素一定是K，這時減法操作一定不會操作在這個元素上，是以加法操作作為逆操作也不會出現在這個元素上。是以此時不存在與第一種回溯操作對應的子序列。

第二種情況：父序列與子序列是通過第二種回溯操作聯系起來的 。

因為子序列變為父序列時，是通過交換來消除最右邊的一個逆序對的。是以由目前序列來得到子序列時，需要在目前序列中找到一個符合條件的增序對，并通過交換操作得到子序列。

但是在這裡，條件是非常複雜的，下面首先通過分析子序列經過第二種回溯操作産生的父序列的性質來判斷目前序列是否有第二種回溯操作下的子序列。

假設子序列為\(c_1 c_2 \cdots c_n\)，其中我們交換的是\(c_j ,c_{j+1}\)，是以對于大于j+1的那些元素是非遞減序列，因為目前交換的是最右邊的逆序對。交換完之後，可能對于大于等j的那些元素形成了新的非遞減序列，甚至更長，也可能\(c_j ,c_{j+2}\)形成了新的逆序對，這些在下面來讨論。

1. 如果生成了新的逆序對

   設目前序列為\(p_1 p_2 \cdots p_n\)，假設\(p_b ,p_{b+1}\)是目前序列中最右邊的一個逆序對。如果這個逆序對是子序列生成父序列的時候生成的新的逆序對，則原來\(c_{j+1}\)的變成了現在的，由于原來的\(c_{j+1},c_{j+2}\)是非逆序對，是以父序列中必須有\(p_{b-1} \leq p_{b+1}\)。如果不符合這個條件，則不可能通過交換這個逆序對前面的那一對數即\(p_{b-1} , p_b\)來得到子序列。如果符合這個條件，則可以通過交換這個\(p_{b-1},p_b\)來得到子序列。

2. 如果沒有生成逆序對

   設目前序列為\(p_1 p_2 \cdots p_n\)，是以要交換相鄰的一個增序對來抵消相應的回溯操作，而且這個順序對的右邊不能有逆序對，否則子序列中交換的不是最右端的逆序對，産生沖突。假設\(p_b,p_{b+1}\)是目前序列中最右邊的逆序對，可以選擇這個對右邊的任何一對來進行交換進而生成子序列。但是這時還要考慮k限制的生長序列的第二個條件，即 \(a_i<MAX(a_1 \cdots a_{i-1}) +1\)。

3. 是以，如果交換的是\(p_i ,p_{i+1}\)，交換完之後的序列是\(p_{i+1} p_i\)。此時如果\(p_{i+1}\)是比目前序列的前(i-1)個數都大的時候，根據生長序列的第二個條件，有\(p_i\leq p_{i+1}+1\)。又因為這兩個數交換之後是逆序對，即\(p_{i+1}>p_i\) 。是以\(p_i \neq p_{i+1}+1\)，此時可以描述為，增序對\(p_i ,p_{i+1}\)都比這兩個元素之前的元素的值大，且\(p_i=p_{i+1}+1\)時沒有子序列。其他情況下都有相應的子序列，即直接把這個增序對交換即可生成子序列。注意在這種情況下，同一個目前序列可生成多個子序列，也可能無法生成子序列。 

綜合生成

通過上面讨論的結果，我們可以遞歸的從根序列下降，不停地生成子序列，直到不能生成為止。由于我們在生成子序列的過程中，第一種生成操作和第二種生成操作都會使用，且在生成過程中保持了k限制的生長序列的性質，是以生成的所有子序列都是一個集合的合理劃分。又因為每個集合的合理劃分都可以回溯到根節點，是以從根序列遞歸生成的所有序列就是所有的合理劃分。而且，我們可以看出每生成一個子序列和每回溯到父序列所需要的時間都是線性有界的，而且每個節點最多周遊兩次。是以，平攤下來的每子序列的生成時間為常量，這就是标題中常量時間的由來。其實，整個生成過程可以了解為一個多叉樹的周遊，如下圖所示。其中，虛線表示的為第一種方式的生成，實線表示的為第二種方式的生成。因為樹的周遊方法有很多種，但是因為根節點要先周遊，是以隻剩下了先序周遊和層序周遊這兩種。

而先序周遊在多叉樹中不怎麼可行，不像二叉樹中可以明确的分為左節點和右節點。是以考慮層序周遊，這時可以使用隊列來進行周遊，但是由于可能于同一層中的節點數太多導緻記憶體不夠的情況出現。是以使用遞歸方法，每得到一個節點，就把目前節點可以生成的所有子節點入棧，然後選擇一個子節點遞歸生成，如果節點沒有子節點則出棧。這樣可以縮小記憶體占用，但是遞歸的成本也是比較大的，值得注意。