07-04全排列问题

给定{ 1, 2, 3, , , n }，其全排列为$n!$个，这是最基础的高中组合数学知识。我们以n=4为例，其全部排列如下图（以字典序树形式来呈现）：

我们很容易想到用递归来求出它的所有全排列。

仔细观察上图，

• 以1开头，下面跟着{ 2, 3, 4 }的全排列；
• 以2开头，下面跟着{ 1, 3, 4 }的全排列；
• 以3开头，下面跟着{ 1, 2, 4 }的全排列；
• 以4开头，下面跟着{ 1, 2, 3 }的全排列。

代码如下：

#include <iostream>
#include <algorithm>

using namespace std;

void FullPermutation(int array[], int left, int right)
{
    if (left == right)
    {
        for (int i = 0; i < 4; i++)
            cout << array[i] << " ";
        cout << endl;
    }
    else
    {
        for (int i = left; i <= right; i++)
        {
            swap(array[i], array[left]);
            FullPermutation(array, left + 1, right);
            swap(array[i], array[left]);
        }
    }
}

int main()
{
    int array[4] = { 1,2,3,4 };
    FullPermutation(array, 0, 3);
    return 0;
}

运行如下：

咦~递归写出的全排列有点不完美，它并不严格遵循字典序。但是熟悉C++的朋友肯定知道另一种更简单，更完美的全排列方法。

定义于文件 <algorithm> 内的两个算法函数：

next_permutation
prev_permutation

#include <iostream>
#include <algorithm>

using namespace std;

void FullPermutation(int array[])
{
    do
    {
        for (int i = 0; i < 4; i++)
            cout << array[i] << " ";
        cout << endl;
    } while (next_permutation(array, array + 4));
}

int main()
{
    int array[4] = { 1,2,3,4 };
    FullPermutation(array);
    return 0;
}

运行结果省略。输出结果正好符合字典序。

那么这个“轮子”是怎么做到的呢？（摘自侯捷的《STL源码剖析》）

• next_permutation ，首先，从最尾端开始往前寻找两个相邻元素，令第一元素为 *i ，第二元素为 *ii ，且满足 *i < *ii ，找到这样一组相邻元素后，再从最尾端开始往前检验，找出第一个大于 *i 的元素，令为 *j ，将i，j元素对调，再将ii之后的所有元素颠倒排列，此即所求之“下一个”排列组合。
• prev_permutation ，首先，从最尾端开始往前寻找两个相邻元素，令第一元素为 *i ，第二元素为 *ii ，且满足 *i > *ii ，找到这样一组相邻元素后，再从最尾端开始往前检验，找出第一个小于 *i 的元素，令为 *j ，将i，j元素对调，再将ii之后的所有元素颠倒排列，此即所求之“上一个”排列组合。

代码如下：

bool next_permutation(int * first, int * last)
{
    if (first == last) return false;  // 空区间
    int * i = first;
    ++i;
    if (i == last) return false;  // 只有一个元素
    i = last;
    --i;

    for (;;)
    {
        int * ii = i;
        --i;
        if (*i < *ii)
        {
            int * j = last;
            while (!(*i < *--j))  // 由尾端往前找，直到遇上比 *i 大的元素
                ;
            swap(*i, *j);
            reverse(ii, last);
            return true;
        }
    }

    if (i == first)  // 当前排列为字典序的最后一个排列
    {
        reverse(first, last);  // 全部逆向排列，即为升序
        return false;
    }
}

bool prev_premutation(int * first, int * last)
{
    if (first == last) return false;  // 空区间
    int * i = first;
    ++i;
    if (i == last) return false;  // 只有一个元素
    i = last;
    --i;

    for (;;)
    {
        int * ii = i;
        --i;
        if (*i > *ii)
        {
            int * j = last;
            while (!(*i > *--j))  // 由尾端往前找，直到遇上比 *i 大的元素
                ;
            swap(*i, *j);
            reverse(ii, last);
            return true;
        }
    }

    if (i == first)  // 当前排列为字典序的第一个排列
    {
        reverse(first, last);  // 全部逆向排列，即为降序
        return false;
    }
}

刚才主要介绍了解决不重复序列的全排列问题的两个方法：递归和字典序法。

那如果是 重复序列 的全排列呢？该如何求解？举个例子，对于一个重复序列{ 1, 2, 2 }，其全排列只有三个：{ 1, 2, 2 }，{ 2, 1, 2 }，{ 2, 2, 1 }。

我们依旧先用递归来求解。

#include <iostream>  
#include <algorithm>  

using namespace std;

bool IsEqual(int array[], int left, int right)
{
    for (int i = left; i < right; i++)
        if (array[i] == array[right])
            return true;
  
    return false;
}

void FullPermutation(int array[], int left, int right)
{
    if (left == right)
    {
        for (int i = 0; i < 3; i++)
            cout << array[i] << " ";
        cout << endl;
    }
    else
    {
        for (int i = left; i <= right; i++)
        {
            if (!IsEqual(array, left, i))
            {
                swap(array[i], array[left]);
                FullPermutation(array, left + 1, right);
                swap(array[i], array[left]);
            }
        }
    }
}

int main()
{

    int array[4] = { 1,2,2 };

    FullPermutation(array, 0, 2);

    return 0;
}

输出如下：

简单说下 IsEqual() 为什么那么写。

考虑重复序列1abc2xyz2，

• 交换1与第一个2，变成了2abc1xyz2，按照程序，接下来对 abc1xyz2 进行全排列；
• 假若1与第二个2交换，变成了2abc2xyz1，按照程序，接下来对 abc2xyz1 进行全排列。

那么问题来了，注意我加粗的两个地方，这两个全排列进行的都是同样的工作，所以必然会造成重复输出。

下面再来看下STL里的 next_permutation 对重复序列的反应。

#include <iostream>  
#include <algorithm>  

using namespace std;

void FullPermutation(int array[])
{
    do
    {
        for (int i = 0; i < 3; i++)
            cout << array[i] << " ";
        cout << endl;
    } while (next_permutation(array, array + 3));
}

int main()
{
    int array[3] = { 1,2,2 };
    FullPermutation(array);
    return 0;
}

运行如下：

从结果来看， next_permutation 的适应性更强，不管是不重复序列还是重复序列，它都可以输出正确的结果。其实这很好理解， next_permutation 的本质是字典序原理，而字典序是严格的大于或者小于，没有等于。