MENU

全排列问题

July 4, 2018 • 技术

给定{ 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;
}

运行如下:

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
1 4 2 3
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
3 1 2 4
3 1 4 2
3 4 1 2
3 4 2 1
4 2 3 1
4 2 1 3
4 3 2 1
4 3 1 2
4 1 3 2
4 1 2 3

咦~递归写出的全排列有点不完美,它并不严格遵循字典序。但是熟悉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;
}

输出如下:

1 2 2
2 1 2
2 2 1

简单说下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;
}

运行如下:

1 2 2
2 1 2
2 2 1

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

Archives QR Code Tip
QR Code for this page
Tipping QR Code