上一篇文章中重点讨论了二进制格雷码。其实从广义上来说，只要相邻的元素只有一位改变的话都可以称之为格雷码。下面就来说一下格雷码在集合分割上的应用。
先讨论一下集合分割的问题。一个集合的分割就是把S分解成若干个子集S1,S2,S3,…,Sn，使得S1∪S2∪S3∪…∪Sn=S；但对于任意两个不同的子集Si和Sj而言，满足Si∩Sj=φ（φ表示空集）。举例来说，
1
2
3
4
5
6
| 集合{1,2,3}的分割有5种，如下
{1},{2},{3}
{1,2},{3}
{1,3},{2}
{2,3},{1}
{1,2,3}
|
先看一下常规解法。为了程序写起来方便一点，我们用Ci表示i的编码值，也就是元素i在哪一个集合中，上面的例子就是从左到右集合的序号从1开始，并且依次递增。当处理到i时，前i-1个数的分割已经确定了，则Ci的取值范围为1到Cj(j=1,2,...,i-1)+1。为什么要加1呢？就是上面例子的第一种情况，i单独表示一个子集。经过分析，我们可以用回溯法来实现程序。先处理n，我们从1遍历到前i-1个集合序列的极大值再加1。然后回溯到n-1，对n-i的每一个集合编码，它后面的值，比如n都需要重新处理。代码写起来还是有点技巧的，大家自己读吧！
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
| void set_partition(int n)
{
int *code, *maxi;
int i, j;
code = (int*)malloc(n*sizeof(int));
maxi = (int*)malloc(n*sizeof(int));
for(i=0; i<n; i++)
{
code[i] = 1;
maxi[i] = 2;
}
while(1)
{
print_partition(code, n);
for(i=n-1; code[i]==maxi[i]; i--)
;
if(i>0){
code[i]++;
for(j=i+1; j<n; j++)
{
code[j] = 1;
maxi[j] = maxi[i]+(code[i]==maxi[i] ? 1 : 0);
}
}
else
break;
}
free(code);
free(maxi);
}
void print_partition(int code[], int n)
{
int i;
for(i=0; i<n; i++)
printf("%3d", code[i]);
printf("\n");
}
|
那么格雷码怎么来处理集合分割呢？ 为了更好的理解，这里先作几个简单的定义。设π是集合{1,2,…,n-1}的任一分割，再定义π的儿子是集合{1,2,…n-1,n}的分割且能够通过π生成。就比如{1,2,3}就是{1,2}的儿子。和格雷码一样，我们这里先考虑递归的方法。假设我们已经得到了集合{1,2,…,n-1}的分割，并且是按格雷码顺序排列的。取出第一种分割，分别将n置于分割的第一个子集，第二个子集，…，最后一个子集中。然后取出集合{1,2,…,n-1}的第二种分割，这时候对n处理用相反的顺序来。然后对下一个分割再正着来，依次下去。举个集合{1,2,3}的例子如下。
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
{1,2,3}
{1,2}{3}
{1}{2}{3}
{1}{2,3}
{1,3}{2}
[/cce_cpp]
我简单写了一个递归的代码实现。
[cce_cpp tab_size="4"]
vector<vector<vector<int> > > partition_gray_recurse(int n)
{
vector<vector<vector<int> > > res;
if(n==1)
{
vector<int> element;
vector< vector<int> > partitions;
vector<vector<vector<int> > > ans;
element.push_back(1);
partitions.push_back(element);
ans.push_back(partitions);
return ans;
}
vector<vector<vector<int> > > ans = partition_gray_recurse(n-1);
int i=0;
while(i<ans.size())
{
vector< vector<int> > partitions = ans[i];
for(int j=0; j<partitions.size(); j++)
{
vector< vector<int> > temp = partitions;
temp[j].push_back(n);
res.push_back(temp);
}
vector<int> element;
element.push_back(n);
vector< vector<int> > temp = partitions;
temp.push_back(element);
res.push_back(temp);
i++;
if(i>=ans.size())
break;
partitions = ans[i];
temp.clear();
temp = partitions;
temp.push_back(element);
res.push_back(temp);
for(int j=partitions.size()-1; j>=0; j--)
{
vector< vector<int> > temp = partitions;
temp[j].push_back(n);
res.push_back(temp);
}
i++;
}
return res;
}
void output_gray(vector<vector<vector<int> > >partitions)
{
if(partitions.empty())
return;
for(int i=0; i<partitions.size(); i++)
{
cout << "{ ";
for(int j=0; j<partitions[i].size(); j++)
{
cout << "(";
for(int k=0; k<partitions[i][j].size(); k++)
cout << partitions[i][j][k] << " ";
cout << ") ";
}
cout << " }" << endl;
}
}
|
代码对于集合{1,2,3,4}的执行结果如下，直观的来看，相邻的分割都可以通过移动一个元素到另外一个子集合或者新建一个子集合得到。至于非递归的实现，大家自己回去写吧！
今天先写这么多。
对了，周末愉快！
参考：《C语言名题精选百则》；Richard KAYE, A gray code for set partitions._ Information Processing Letters_, 1976(5), pp.171~173