C++代码（4）排列与组合
书接上回，继全排列之后，接下来的任务自然是要给我们的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 // 同未参与部分排列的
补充：软件开发 , C++ ,
