書接上回，繼全排列之后，接下來的任務自然是要給我們的Permutation添加上部分排列的功能。所謂的部分排列，為了便于行文的展開，我也不怕再舉例，比如，針對0到4這5個數的P(3,5)，其排列如下：012，013，014，021，023，024，……，234，240，241，……，431，432。可以看到，其排列編號順序與全排列類似，任何一個部分排列有且只有一個后繼排列，好比240的下一位必然是241，123的下一位必須是201，所以我們完全可以采取同樣的辦法來處理部分排列。
新的Permutation要能部分排列，用戶必須將P(N,M)中N，M以某種方式告知Permutation，最恰當的地方就在Permutation的構造函數中傳進去，原本只接受一個參數的構造函數，現在要接收兩個參數了，同時，Permutation中除了保存N，還要保存M，因此，升級后的Permutation的定義如下。
class Permutation
{
public:
enum {MAX_SIZE = 10};
Permutation(int nTotal, int nPart)
{
assert(0 < nTotal && nTotal < MAX_SIZE);
assert(0 < nPart && nPart <= nTotal);
m_nPart = (char)nPart;
m_nTotal = (char)nTotal;
for (char i=0; i<m_nTotal; i++)
m_Indexs[i] = i;
}
public:
bool ToNext();
char operator[] (int n)const
{
assert(0 <= n && n <= m_nPart);
return m_Indexs[n];
}
private:
char m_Indexs[MAX_SIZE];
char m_nPart;
char m_nTotal;
};
很明顯，必須在ToNext上大做文章。如果說全排列的ToNext稍微有一點點復雜，那么部分排列的ToNext就應該是很有點復雜，算法設計起來也不難，難的是如何用代碼簡潔地表達出來。請大家別急著看下去，先自己思考思考，這是一個很好的鍛煉機會。
……，省略了思考的過程，其實也沒什么，只要寫幾個部分排列的后繼，就發現了其變化規律，就是先確定要改變的元素，然后保證跟在其后的數為最小，還是舉例說明，P(9,5)中42876，其后繼為43012，先找到41876中第1位即2要變成3，然后取剩下來的[0125678]中的012，置放于43之后。
先考察尾數，無非分為兩種情況。
1、只變化尾數，如P(8,4)，0125，0126，0127，求其后繼排列的代碼最容易編寫了，只要注意到[0125|3467]，5變為6，6是3467中，從后往前算，最后一個比5大的元素。更有意思的是，交換5，6之后，3457依然保持升序的樣子。
2、不只改變尾數，這是因為尾數要比未參與到部分排列中的元素要大，好比P(8,4)，7605的下一位為7810，注意到[7605|1234]，5大過1234。因此，必須考察5之后的0了，也即倒數第2位。同樣，又分為兩種情況。
1）、改變倒數第2位。其改變方式又有兩種：1、交換未參與排列的元素，如[7605|1234]，交換0與1；2、交換參與排列的元素，如[7645|0123]，7645變成7654。
2）、不僅僅改變倒數第2位，這是因為尾數第2位大于尾數和未參與到部分排列中的元素，好比P(8,5)，23476的下一位為23501，同樣又分為兩種情況。
……，以此類推，直到找不到要參與交換的元素，部分排列完成。
bool Permutation::ToNext()
{
if (m_nPart == m_nTotal)
{
// 為全排列
// ……
return;
}
char nToSwap = m_nPart-1;
char nLeft = m_nTotal - 1;
if (m_Indexs[nLeft] > m_Indexs[nToSwap]) // 只改變尾數
{
while (nLeft > nToSwap && m_Indexs[nLeft]>m_Indexs[nToSwap])
nLeft--;
nLeft++;
swap(m_Indexs[nToSwap], m_Indexs[nLeft]);
return true;
}
while (nToSwap > 0 && m_Indexs[nToSwap]<m_Indexs[nToSwap-1] && m_Indexs[nToSwap]>m_Indexs[nLeft])
nToSwap--;
if (nToSwap == 0) // 部分排列業已完成
return false;
nToSwap--; // 已確定這個位置要參與交換了
if (m_Indexs[nToSwap] > m_Indexs[nLeft]) // 同參與部分排列的元素交換
{
char nReplace = m_nPart - 1;
while (m_Indexs[nReplace] < m_Indexs[nToSwap])
nReplace--;
swap(m_Indexs[nToSwap], m_Indexs[nReplace]);
}
else // 同未參與部分排列的元素交換
{
while (nLeft >= m_nPart && m_Indexs[nLeft]>m_Indexs[nToSwap])
nLeft--;
nLeft++;
swap(m_Indexs[nToSwap], m_Indexs[nLeft]);
}
sort(m_Indexs+nToSwap+1, m_Indexs+m_nTotal);// 后面為剩下來的最小排列數
return true;
} 其實，根據排列的公式P(N, M)=N*P(N-1,M-1)，很容易就可以寫出P(N, M)的遞歸函數了。
void permutation(int* pSet, int n, int m)
{
permutationImp(pSet, n, m, m);
}
void permutationImp(int* pSet, int n, int m, int M)
{
if (m == 0)
{
int* pFullSet = pSet-M;
for (int i=0; i<M; i++)
cout << pFullSet[i] << " ";
cout << endl;
return;
}
for (int i=0; i<n; i++)
{
swap(pSet[0], pSet[i]);
permutationImp(pSet+1, n-1, m-1, M);
swap(pSet[0], pSet[i]);
}
}
非常簡潔明了，這真讓人沮喪，相比于Permutation的ToNext的種種煩雜，它無疑極具殺傷力。同樣都是在搞排列，為何遞歸函數可以如此的簡單呢？只因編譯器幫遞歸干了很多事情，而ToNext中，我們必須事事親歷親為。其實這也是遞歸與非遞歸的一大差別，遞歸中以一點點效率和靈活來換取代碼的簡潔易懂，而非遞歸則能以各種各樣的方法來獲取種種靈活與效率，編程就是這樣，無非是在做各種各樣的妥協。此外，Permutation的輸出好看一點，更具規律，嚴格按照我們的要求來輸出，這也能稍稍地自我安慰一下吧。
依此編號的順序算法，好比，C(4,3)，其編號為012，013，023，123，不難設計出一個Combination，而且其ToNext要比部分排列的ToNext簡單得多，只要注意到組合數中小的元素必然在前面，例如只存在012的組合，不存在120、102、021等組合數，因為它們都與012為同一個組合數，參考部分排列的代碼，很容易就可寫出Combination的代碼。24點算法涉及的組合只為C(N,2)，雖然C(N,2)為C(N,M)的特例，但基于時間與空間等效率的考慮，我更傾向于重新設計一個Combination2專門用來對付C(N,2)。其實算法的設計，不過是時間與空間的交換、復雜與簡單的交換、通用與專用的交換，此三項的權衡而已。下面是Combination2的代碼，非常簡單，我也不想說太多。
class Combination2
{
public:
Combination2(int count)
{
assert(count >= 2);
m_nCount = (char)count;
m_Indexs[0] = 0;
m_Indexs[1] = 1;
}
public:
char operator[](int n)const
{
assert(0<=n && n<2);
return m_Indexs[n];
}
bool ToNext();
private:
char m_Indexs[2];
char m_nCount;
};
bool Combination2::ToNext()
{
if (m_Indexs[0] == m_nCount-1 && m_Indexs[1] == m_nCount-2)
return false;
if (m_Indexs[1] < m_nCount-1)
{
m_Indexs[1]++;
if (m_Indexs[1] == m_Indexs[0])
m_Indexs[1]++;
}
else
{
m_Indexs[0]++;
m_Indexs[1] = 0;
}
return true;
} 至此，終于圓滿解決了排列與組合的問題，但其實都沒多大的作用，對于不重復集合的排列與組合，只要用公式一乘，就出來結果了。研究可重復集合的排列與組合，可能還有點作用，其設計與代碼編寫，也很有意思，我就不再羅嗦了。