微信号:TheAlgorithm

介绍:算法与数据结构知识、资源分享

详解全排列算法

2018-03-14 08:30 刘毅

作者:刘毅

https://61mon.com/index.php/archives/197/


简介


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



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


仔细观察上图,


以 1 开头,下面跟着 {2, 3, 4} 的全排列;


以 2 开头,下面跟着 {1, 3, 4} 的全排列;


以 3 开头,下面跟着 {1, 2, 4} 的全排列;


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


代码如下:


/**

*

* author : 刘毅(Limer)

* date   : 2017-05-31

* mode   : C++

*/

 

#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> 内的两个算法函数:


1、next_permutation,对于当前的排列,如果在字典序中还存在下一个排列,返回真,并且把当前排列调整为下一个排列;如果不存在,就把当前排列调整为字典序中的第一个排列(即递增排列),返回假。


2、prev_permutation,对于当前的排列,如果在字典序中还存在上一个排列,返回真,并且把当前排列调整为上一个排列;如果不存在,就把当前排列调整为字典序中的最后一个排列(即递减排列),返回假。


/**

*

* author : 刘毅(Limer)

* date   : 2017-05-31

* mode   : C++

*/

 

#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 源码剖析》)


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


2、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;

    }

}


结后语


这篇文章主要介绍了解决不重复序列的全排列问题的两个方法:递归和字典序法



●本文编号604,以后想阅读这篇文章直接输入604即可

●输入m获取文章目录

推荐↓↓↓
 

Python编程

更多推荐:18个技术类微信公众号

涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。

 
算法与数据结构 更多文章 别人Python都玩腻了,而你却连安装工具库都搞不清楚! 互联网公司有哪些奇葩面试题? 图论的各种基本算法 2018 年 2 月份 GitHub 上最热门的开源项目 漫画:什么是MapReduce?
猜您喜欢 女生节礼物!手慢无! 注重细节设计:动作按钮,没你想的那么简单 腾讯旅游做的小程序,让记账也能成为一种享受 | 知晓程序 · MINA&nb [SSD番外篇]宋瓷 开发后台系统会用到什么?