书接上回，继全排列之后，接下来的任务自然是要给我们的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;
} 至此，终于圆满解决了排列与组合的问题，但其实都没多大的作用，对于不重复集合的排列与组合，只要用公式一乘，就出来结果了。研究可重复集合的排列与组合，可能还有点作用，其设计与代码编写，也很有意思，我就不再罗嗦了。