我们将使用分治法实现一个全排列算法。先来看一下算法实现后的效果:
['a','b','c']. permutation ["a", "b", "c"], ["a", "c", "b"], ["b", "a", "c"], ["b", "c", "a"], ["c", "b", "a"], ["c", "a", "b"]。
注意最后两项,我先以为可以用nextpermutation实现的,后来发现分治法求出的排序和nextpermutation并不一样。
算法描述
分治法求解问题分为三个步骤: - 分解:将问题分为若干个子问题。 - 解决:递归地求解每个子问题。 - 合并:将每个子问题的解合并成为整个问题的解。
现在我们需要求具有n个元素的数组A的全排列。例如:大小为3的数组A=[a,b,c] (为方便起见,我把引号全都省略了,其实应该是A=['a','b','c']。下同),它的全排列为: [[a,b,c], [a,c,b], [b,a,c], [b,c,a], [c,a,b], [c,b,a]] 这是一个大小为 n!*n 的二维数组。
使用分治算法求解全排列的过程如下 - 分解:将数组分为子数组 A[1..k-1] 和一个元素 A[k]。 (1≤k≤n) - 解决:递归地求解每个子数组 A[1..k-1] 的全排列,直至子数组A[1..k-1]为空时结束递归。 - 合并:将上一步的结果---A[1..k-1]的全排列(一个二维数组)与元素A[k]合并,得出A[1..k]的全排列。例如: [[]] 与 a 合并得到 [[a]] [[a]] 与 b 合并得到 [[a,b], [b,a]] [[a,b],[b,a]] 与 c 合并得到 [[a,b,c],[a,c,b],[c,a,b],[b,c,a],[c,a,b],[c,b,a]]
看下面的图示会更直观一些
- 分解过程
[a,b,c] / \ [a,b] c / \ [a] b / \ [] a
- 合并过程
[] a \ / [[a]] b \ / [[a,b],[b,a]] c \ / [[a,b,c], [a,c,b], [c,a,b], [b,a,c], [b,c,a], [c,b,a]]
#include
#include
using namespace std;
#define N 4
char str[10];
void Perm(char *str, int k, int m);
void Swap(char &a;, char &b;);
int main()
{
int n;
while(scanf("%d", &n;) != EOF)
{
for(int i=0; i<=n; ++i)
{
str[i] = i+'0';
}
Perm(str, 1, n);
}
return 0;
}
void Perm(char *str, int k, int m)
{
int i;
if(k == m)
{
for(i=1; i<=m; ++i)
cout<BUCT OJ 1140 分治法求解全排列问题的解答报告
但是对于字符串中存在重复的,比较1123,网上给出了这个源码:
[http://fayaa.com/code/view/13115/](http://fayaa.com/code/view/13115/)
```cpp
#include
#include
using namespace std;
#define N 4
void Swap(char *pa, char *pb);
void FullPermutation(char *str, int k, int n);
int IsAppeared(char *str, char t, int begin, int end);
char str[N+1] = "ADCD";
int main()
{
FullPermutation(str, 0, N);
return 0;
}
void Swap(char *pa, char *pb)
{
if(pa != pb)
{
char tmp = *pa;
*pa = *pb;
*pb = tmp;
}
}
//判断字符t在字符串的下标begin到end处是否出现过
int IsAppeared(char *str, char t, int begin, int end)
{
for(int j=begin; j<=end; ++j)
{
if(t == str[j])
return 1;
}
return 0;
}
/*对字符串进行全排列,注意该函数处理了字符重复的情况,字符重复的情况有两种:
1. str[i]本身和后面的str[k]相同
2. str[k]在k+1到i-1的下标之间已经出现过(用IsAppeared()函数去判断)
*/
void FullPermutation(char *str, int k, int n)
{
if(k == n)
{
cout<<str<<endl;
return;
}
for(int i=k; i<n; ++i)
{
if(i!=k && (str[i]==str[k]) || IsAppeared(str,str[i],k+1,i-1)) ////用以处理元素重复的情况
continue;
Swap(str+k, str+i);
FullPermutation(str, k+1, n);
Swap(str+k, str+i);
}
}