@songpfei
2015-12-31T17:36:47.000000Z
字数 4335
阅读 3030
OJ_算法
全排列在很多程序都有应用,是一个很常见的算法,常规的算法是一种递归的算法,这种算法的得到基于以下的分析思路。 给定一个具有n个元素的集合(n>=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]);
}
}
}
对一个给定数据进行全排列,在各种场合经常会用到。组合数学中,生成全排列的方法有很多,卢开澄老师的《组合数学》中就介绍了三种:序数法,字典序法,临位互换法等。其中以字典序法由于算法简单,并且使用的时候可以依照当前状态获取下一个状态,直到所有排列全部完成,方便在程序中随要随用,应用比较广泛,STL中的Next_permutation也是使用此法。
字典序,顾名思义就是按照字典的顺序(a-z, 1-9)。以字典序为基础,我们可以得出任意两个数字串的大小。比如 "1" < "12"<"13"。 就是按每个数字位逐个比较的结果。对于一个数字串,“123456789”, 可以知道最小的串是 从小到大的有序串“123456789”,而最大的串是从大到小的有序串“*987654321”。这样对于“123456789”的所有排列,将他们排序,即可以得到按照字典序排序的所有排列的有序集合。
如此,当我们知道当前的排列时,要获取下一个排列时,就可以范围有序集合中的下一个数(恰好比他大的)。比如,当前的排列时“123456879”, 那么恰好比他大的下一个排列就是“123456897”。 当当前的排列时最大的时候,说明所有的排列都找完了。
字典序法求全排列步骤:
设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,依然未找到,此时所有全排列都找完,其数字串从大到小排序
#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;
}
求全排列,递归算法效率太低,所以采用非递归的字典序法实现排列。这个算法已经在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'
1234
其下一个字典序为1243,即在初始字符串为时,执行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