分治法实现全排列

我们将使用分治法实现一个全排列算法。先来看一下算法实现后的效果:

[‘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);
    }
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《分治法实现全排列》有6个想法

  1. Fairly nice write-up. I just Digging your site and desired to say that I’ve actually enjoyed studying your blogpost. Any means I’ll be signing as much as your feed and I believe you’ll post as soon as more within the near future.

发表评论

电子邮件地址不会被公开。 必填项已用*标注