全排列算法

OJ_算法

  全排列在很多程序都有应用，是一个很常见的算法，常规的算法是一种递归的算法，这种算法的得到基于以下的分析思路。 给定一个具有n个元素的集合（n>=1），要求输出这个集合中元素的所有可能的排列。

1. 递归实现

例如，如果集合是{a,b,c},那么这个集合中元素的所有排列是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}，显然，给定n个元素共有n!种不同的排列，如果给定集合是{a,b,c,d}，可以用下面给出的简单算法产生其所有排列，即集合(a,b,c,d)的所有排列有下面的排列组成：
（1）以a开头后面跟着(b,c,d)的排列
（2）以b开头后面跟着(a,c,d)的排列
（3）以c开头后面跟着(a,b,d)的排列
（4）以d开头后面跟着(a,b,c)的排列，这显然是一种递归的思路，于是我们得到了以下的实现：
即：对于有n个元素的集合的排列T(n)时，分别以集合的每个元素作为第一个位置的元素，然后求剩下n-1个元素的全排列T(n-1);重复递归，知道集合只有一个元素T(1),其全排列为元素本身。
所以：
1. 递归方程为： T(n)=n*T(n-1)
2. 递归结束条件： 元素个数为1，结束；

算法实现：

/*************************************
function: 求字符串的全排列
input param:
char *a :字符串
k:递归层次（确定第k个位置的元素）
n:字符串元素个数
**************************************/
void permutation(char* a,int k,int n)  
{  
    int i,j;  
    if(k == n-1)  
    {  
        for(i=0;i<n;i++)  
            cout<<a[i];  
        cout<<endl;  
    }  
    else  
    {  
        for(j=k;j<n;j++)  
        {  
            swap(a[j],a[k]);  
            permutation(a,k+1,n);  
            swap(a[j],a[k]);  
        }  
    }  
}  

2. 非递归算法（字典序法）

  对一个给定数据进行全排列，在各种场合经常会用到。组合数学中，生成全排列的方法有很多，卢开澄老师的《组合数学》中就介绍了三种：序数法，字典序法，临位互换法等。其中以字典序法由于算法简单，并且使用的时候可以依照当前状态获取下一个状态，直到所有排列全部完成，方便在程序中随要随用，应用比较广泛，STL中的Next_permutation也是使用此法。

2.1 算法定义

字典序，顾名思义就是按照字典的顺序（a-z, 1-9）。以字典序为基础，我们可以得出任意两个数字串的大小。比如 "1" < "12"<"13"。 就是按每个数字位逐个比较的结果。对于一个数字串，“123456789”， 可以知道最小的串是 从小到大的有序串“123456789”，而最大的串是从大到小的有序串“*987654321”。这样对于“123456789”的所有排列，将他们排序，即可以得到按照字典序排序的所有排列的有序集合。
如此，当我们知道当前的排列时，要获取下一个排列时，就可以范围有序集合中的下一个数（恰好比他大的）。比如，当前的排列时“123456879”， 那么恰好比他大的下一个排列就是“123456897”。 当当前的排列时最大的时候，说明所有的排列都找完了。

2.2 算法步骤

字典序法求全排列步骤：
设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn（即开始时字符串必须进行升序排列，使其成为全排列的第一个串（最小串）)
1. 从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i|pi<pi+1}
2. 在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pi>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）
3. 对换pj，pk
4. 再将pj+1......pk-1pkpk+1......pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个排列。
5. 返回至步骤1重复进行，直到步骤1,i=0,依然未找到，此时所有全排列都找完，其数字串从大到小排序

2.3 字典序算法实现

#include<string>
#include<algorithm>
using namespace std;
/*******************************
function:字典序全排列
********************************/
void LexicographicalOrderPermutation(string &input,vector<string>&output)
{
    if (!output.empty())
        output.clear();
    if (input.size()==0)
        return;
    if (input.size() == 1)
    {
        output.push_back(input);
        return;
    }
    sort(input.begin(), input.end());
    output.push_back(input);//字典序全排列的第一个值
    string::iterator it_j,it_k,it_i = input.end()-2;
    while (it_i!=input.end())
    {
        if (*it_i < *(it_i + 1))//1. 从最右边开始找第一个比右边数字小的数字的序号j,即j=max{i|pi<pi+1}
        {
            it_j = it_i;
            do
            {
             ++it_i;
            } while (it_i!=input.end()&&(*it_j < *it_i));//2. 在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pi>pj}
            it_k = it_i - 1;
            swap(*it_j, *it_k);//3. 对换pj,pk
            reverse(it_j + 1, input.end());//4. 倒转pk+1....pn
            output.push_back(input);//5.得到一个全排列，输出
            it_i = input.end() - 2;//重新从最右边开始搜索
        }
        else
        {
            if (it_i == input.begin())
                break;
            --it_i;
        }
    }
}
int main()
{
    string a;
    vector<string> per;
    do 
    {
        cin >> a;
        LexicographicalOrderPermutation(a, per);
        for (vector<string>::const_iterator it = per.begin(); it != per.end(); ++it)
        {
            cout << *it << endl;
        }
    } while (a.size());
    system("pause");
    return 0;
}

3. STL算法

求全排列，递归算法效率太低，所以采用非递归的字典序法实现排列。这个算法已经在c++的STL中实现；

在<algorithm>中，有两个库函数：pre_permutation与next_permutation

重点解析next_permutation;
函数原型:

template<class BidirectionalIterator>
   bool next_permutation(
      BidirectionalIterator _First, 
      BidirectionalIterator _Last
   );
template<class BidirectionalIterator, class BinaryPredicate>
   bool next_permutation(
      BidirectionalIterator _First, 
      BidirectionalIterator _Last,
      BinaryPredicate _Comp
   );

next_permutation(first,last),求的字符串的下一个字典序排列，如成功，返回true,失败返回false.
例如：字符串 1234'
其下一个字典序为1243，即在初始字符串为1234时，执行next_permutation,返回true,同时字符串被改为1243`.而pre_permutation与next_permutation刚好相反，其求取字符串字典序的上一个排列。
由以上可知，如想求得一个字符串的全排列，只需将字符串升序排列（所得字符串为字典序排列的最小排列），然后反复执行next_permutation,直到返回为false,即所有字符串倒序，已找到最大字典序排列。
求字典序全排列代码如下：

#include <iostream>
#include<string>
#include<algorithm>
using namespace std;
 void LexicographicalOrderPermutationBySTL(string &input, vector<string>&output)
{
    if (!output.empty())
        output.clear();
    string::iterator it_first, it_last;
    it_first= input.begin();
    it_last = input.end();
    if (it_first == it_last)
        return;//input为空
    sort(it_first, it_last);
    do
    {
        output.push_back(input);
    } while (next_permutation(it_first,it_last));
}
int main()
{
    string a;
    vector<string> per;
    do 
    {
        cin >> a;
        LexicographicalOrderPermutationBySTL(a, per);
        for (vector<string>::const_iterator it = per.begin(); it != per.end(); ++it)
        {
            cout << *it << endl;
        }
    } while (a.size());
    system("pause");
    return 0;
}

参考：
1. http://blog.csdn.net/hackbuteer1/article/details/6657435
2. http://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html
3. 字典序法：http://blog.csdn.net/cpfeed/article/details/7376132