[关闭]
@songpfei 2015-12-31T09:36:47.000000Z 字数 4335 阅读 2134

全排列算法

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,结束;

算法实现:

  1. /*************************************
  2. function: 求字符串的全排列
  3. input param:
  4. char *a :字符串
  5. k:递归层次(确定第k个位置的元素)
  6. n:字符串元素个数
  7. **************************************/
  8. void permutation(char* a,int k,int n)
  9. {
  10. int i,j;
  11. if(k == n-1)
  12. {
  13. for(i=0;i<n;i++)
  14. cout<<a[i];
  15. cout<<endl;
  16. }
  17. else
  18. {
  19. for(j=k;j<n;j++)
  20. {
  21. swap(a[j],a[k]);
  22. permutation(a,k+1,n);
  23. swap(a[j],a[k]);
  24. }
  25. }
  26. }

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 字典序算法实现

  1. #include<string>
  2. #include<algorithm>
  3. using namespace std;
  4. /*******************************
  5. function:字典序全排列
  6. ********************************/
  7. void LexicographicalOrderPermutation(string &input,vector<string>&output)
  8. {
  9. if (!output.empty())
  10. output.clear();
  11. if (input.size()==0)
  12. return;
  13. if (input.size() == 1)
  14. {
  15. output.push_back(input);
  16. return;
  17. }
  18. sort(input.begin(), input.end());
  19. output.push_back(input);//字典序全排列的第一个值
  20. string::iterator it_j,it_k,it_i = input.end()-2;
  21. while (it_i!=input.end())
  22. {
  23. if (*it_i < *(it_i + 1))//1. 从最右边开始找第一个比右边数字小的数字的序号j,即j=max{i|pi<pi+1}
  24. {
  25. it_j = it_i;
  26. do
  27. {
  28. ++it_i;
  29. } while (it_i!=input.end()&&(*it_j < *it_i));//2. 在pj的右边的数字中,找出所有比pj大的数中最小的数字pk,即 k=max{i|pi>pj}
  30. it_k = it_i - 1;
  31. swap(*it_j, *it_k);//3. 对换pj,pk
  32. reverse(it_j + 1, input.end());//4. 倒转pk+1....pn
  33. output.push_back(input);//5.得到一个全排列,输出
  34. it_i = input.end() - 2;//重新从最右边开始搜索
  35. }
  36. else
  37. {
  38. if (it_i == input.begin())
  39. break;
  40. --it_i;
  41. }
  42. }
  43. }
  44. int main()
  45. {
  46. string a;
  47. vector<string> per;
  48. do
  49. {
  50. cin >> a;
  51. LexicographicalOrderPermutation(a, per);
  52. for (vector<string>::const_iterator it = per.begin(); it != per.end(); ++it)
  53. {
  54. cout << *it << endl;
  55. }
  56. } while (a.size());
  57. system("pause");
  58. return 0;
  59. }

3. STL算法

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

<algorithm>中,有两个库函数:pre_permutation与next_permutation

重点解析next_permutation;
函数原型:

  1. template<class BidirectionalIterator>
  2. bool next_permutation(
  3. BidirectionalIterator _First,
  4. BidirectionalIterator _Last
  5. );
  6. template<class BidirectionalIterator, class BinaryPredicate>
  7. bool next_permutation(
  8. BidirectionalIterator _First,
  9. BidirectionalIterator _Last,
  10. BinaryPredicate _Comp
  11. );

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

  1. #include <iostream>
  2. #include<string>
  3. #include<algorithm>
  4. using namespace std;
  5. void LexicographicalOrderPermutationBySTL(string &input, vector<string>&output)
  6. {
  7. if (!output.empty())
  8. output.clear();
  9. string::iterator it_first, it_last;
  10. it_first= input.begin();
  11. it_last = input.end();
  12. if (it_first == it_last)
  13. return;//input为空
  14. sort(it_first, it_last);
  15. do
  16. {
  17. output.push_back(input);
  18. } while (next_permutation(it_first,it_last));
  19. }
  20. int main()
  21. {
  22. string a;
  23. vector<string> per;
  24. do
  25. {
  26. cin >> a;
  27. LexicographicalOrderPermutationBySTL(a, per);
  28. for (vector<string>::const_iterator it = per.begin(); it != per.end(); ++it)
  29. {
  30. cout << *it << endl;
  31. }
  32. } while (a.size());
  33. system("pause");
  34. return 0;
  35. }

参考:
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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注