書接上回，繼全排列之后，接下來的任務(wù)自然是要給我們的Permutation添加上部分排列的功能。所謂的部分排列，為了便于行文的展開，我也不怕再舉例，比如，針對(duì)0到4這5個(gè)數(shù)的P(3,5)，其排列如下：012，013，014，021，023，024，……，234，240，241，……，431，432。可以看到，其排列編號(hào)順序與全排列類似，任何一個(gè)部分排列有且只有一個(gè)后繼排列，好比240的下一位必然是241，123的下一位必須是201，所以我們完全可以采取同樣的辦法來處理部分排列。
新的Permutation要能部分排列，用戶必須將P(N,M)中N，M以某種方式告知Permutation，最恰當(dāng)?shù)牡胤骄驮赑ermutation的構(gòu)造函數(shù)中傳進(jìn)去，原本只接受一個(gè)參數(shù)的構(gòu)造函數(shù)，現(xiàn)在要接收兩個(gè)參數(shù)了，同時(shí)，Permutation中除了保存N，還要保存M，因此，升級(jí)后的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稍微有一點(diǎn)點(diǎn)復(fù)雜，那么部分排列的ToNext就應(yīng)該是很有點(diǎn)復(fù)雜，算法設(shè)計(jì)起來也不難，難的是如何用代碼簡潔地表達(dá)出來。請(qǐng)大家別急著看下去，先自己思考思考，這是一個(gè)很好的鍛煉機(jī)會(huì)。
……，省略了思考的過程，其實(shí)也沒什么，只要寫幾個(gè)部分排列的后繼，就發(fā)現(xiàn)了其變化規(guī)律，就是先確定要改變的元素，然后保證跟在其后的數(shù)為最小，還是舉例說明，P(9,5)中42876，其后繼為43012，先找到41876中第1位即2要變成3，然后取剩下來的[0125678]中的012，置放于43之后。
先考察尾數(shù)，無非分為兩種情況。
1、只變化尾數(shù)，如P(8,4)，0125，0126，0127，求其后繼排列的代碼最容易編寫了，只要注意到[0125|3467]，5變?yōu)?，6是3467中，從后往前算，最后一個(gè)比5大的元素。更有意思的是，交換5，6之后，3457依然保持升序的樣子。
2、不只改變尾數(shù)，這是因?yàn)槲矓?shù)要比未參與到部分排列中的元素要大，好比P(8,4)，7605的下一位為7810，注意到[7605|1234]，5大過1234。因此，必須考察5之后的0了，也即倒數(shù)第2位。同樣，又分為兩種情況。
1）、改變倒數(shù)第2位。其改變方式又有兩種：1、交換未參與排列的元素，如[7605|1234]，交換0與1；2、交換參與排列的元素，如[7645|0123]，7645變成7654。
2）、不僅僅改變倒數(shù)第2位，這是因?yàn)槲矓?shù)第2位大于尾數(shù)和未參與到部分排列中的元素，好比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]) // 只改變尾數(shù)
{
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) // 部分排列業(yè)已完成
return false;
nToSwap--; // 已確定這個(gè)位置要參與交換了
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);// 后面為剩下來的最小排列數(shù)
return true;
} 其實(shí)，根據(jù)排列的公式P(N, M)=N*P(N-1,M-1)，很容易就可以寫出P(N, M)的遞歸函數(shù)了。
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的種種煩雜，它無疑極具殺傷力。同樣都是在搞排列，為何遞歸函數(shù)可以如此的簡單呢？只因編譯器幫遞歸干了很多事情，而ToNext中，我們必須事事親歷親為。其實(shí)這也是遞歸與非遞歸的一大差別，遞歸中以一點(diǎn)點(diǎn)效率和靈活來換取代碼的簡潔易懂，而非遞歸則能以各種各樣的方法來獲取種種靈活與效率，編程就是這樣，無非是在做各種各樣的妥協(xié)。此外，Permutation的輸出好看一點(diǎn)，更具規(guī)律，嚴(yán)格按照我們的要求來輸出，這也能稍稍地自我安慰一下吧。
依此編號(hào)的順序算法，好比，C(4,3)，其編號(hào)為012，013，023，123，不難設(shè)計(jì)出一個(gè)Combination，而且其ToNext要比部分排列的ToNext簡單得多，只要注意到組合數(shù)中小的元素必然在前面，例如只存在012的組合，不存在120、102、021等組合數(shù)，因?yàn)樗鼈兌寂c012為同一個(gè)組合數(shù)，參考部分排列的代碼，很容易就可寫出Combination的代碼。24點(diǎn)算法涉及的組合只為C(N,2)，雖然C(N,2)為C(N,M)的特例，但基于時(shí)間與空間等效率的考慮，我更傾向于重新設(shè)計(jì)一個(gè)Combination2專門用來對(duì)付C(N,2)。其實(shí)算法的設(shè)計(jì)，不過是時(shí)間與空間的交換、復(fù)雜與簡單的交換、通用與專用的交換，此三項(xiàng)的權(quán)衡而已。下面是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;
} 至此，終于圓滿解決了排列與組合的問題，但其實(shí)都沒多大的作用，對(duì)于不重復(fù)集合的排列與組合，只要用公式一乘，就出來結(jié)果了。研究可重復(fù)集合的排列與組合，可能還有點(diǎn)作用，其設(shè)計(jì)與代碼編寫，也很有意思，我就不再羅嗦了。