使用分治法實現一個全排列算法。先來看一下算法實現后的效果：
['a','b','c'].
permutation
["a", "b", "c"],
["a", "c", "b"],
["b", "a", "c"],
["b", "c", "a"],
["c", "b", "a"],
["c", "a", "b"]。
注意最后兩項，我先以為可以用next_permutation實現的，后來發現分治法求出的排序和next_permutation并不一樣。
算法描述
分治法求解問題分為三個步驟：
- 分解：將問題分為若干個子問題。
- 解決：遞歸地求解每個子問題。
- 合并：將每個子問題的解合并成為整個問題的解。
現在我們需要求具有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]]
看下面的圖示會更直觀一些
1. 分解過程
[a,b,c]
/ \
[a,b] c
/ \
[a] b
/ \
[] a
2. 合并過程
[] 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]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <cstring>
#include <iostream>
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<<str[i]<<" "<<flush;
cout<<endl;
return;
}
for(i=k; i<=m; ++i)
{
Swap(str[k], str[i]);
Perm(str, k+1, m);
Swap(str[k], str[i]);
}
}
void Swap(char &a, char &b)
{
char tmp = a;
a = b;
b = tmp;
}
|
以上也是BUCT OJ 1140 分治法求解全排列問題的解答報告
但是對于字符串中存在重復的，比較1123,網上給出了這個源碼：
http://fayaa.com/code/view/13115/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <iostream>
#include <cstring>
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);
}
}
|