本文章讨论的是将一个包含n个不同元素的集合分割为所有的s个不为空的集合，且每次生成的s个集合不需要考虑顺序关系。相关的背景内容在我的倒数第四篇博客中已经说了，这篇文章主要是贴代码。
1 #include <stdio.h> 2 #include <malloc.h> 3 #define SET 6 4 #define PART 3 5 //这里我们执行的时候用先进先出队列来模拟整个的生成情况 6 struct set_par_link 7 { 8 int* new_set;//代表当前的生成的集合划分 9 struct set_par_link* next_set_par;//代表的是另外的一个集合划分 10 }; 11 struct set_par_link* set_par_link_head=NULL; 12 struct set_par_link* set_par_link_rear=NULL; 13 int* standard_set_par;//代表的是初始的集合划分 14 //这两个是整个链表的头部与尾部，用来插入与删除,初始化为空. 15 void output(int* new_set)//输出函数,给定开始地址。 16 { 17 int for_i,for_j; 18 for (for_i = 0; for_i < SET; for_i++) 19 { 20 printf("%d ", new_set[for_i]); 21 } 22 printf(" "); 23 for(for_i=1;for_i<=PART;for_i++) 24 { 25 printf("("); 26 for (for_j = 0; for_j < SET; for_j++) 27 { 28 if (new_set[for_j] == for_i) 29 { 30 printf("%d ", for_j+1); 31 } 32 } 33 printf(") "); 34 } 35 printf(" "); 36 } 37 void insert_new_set_par(int* new_set_par) 38 { 39 struct set_par_link* new_set_par_link; 40 new_set_par_link = (struct set_par_link*)malloc(sizeof(struct set_par_link)); 41 new_set_par_link->new_set = new_set_par; 42 new_set_par_link->next_set_par = NULL; 43 if (set_par_link_head == NULL) 44 { 45 set_par_link_head = set_par_link_rear = new_set_par_link; 46 } 47 else 48 { 49 set_par_link_rear->next_set_par = new_set_par_link; 50 set_par_link_rear = new_set_par_link; 51 } 52 } 53 int type_one(int* father_set_par)//对当前的集合划分做第一种操作的逆操作 54 { 55 int for_i,reverse,equal;//equal是用来记录第一个相等的对，reverse是用来记录第一个逆序的对 56 int* new_set_par; 57 new_set_par = (int*) malloc(sizeof(int) *SET); 58 for (for_i = 0; for_i < SET; for_i++) 59 { 60 new_set_par[for_i] = father_set_par[for_i]; 61 } 62 for_i=SET-2; 63 equal=reverse=-1; 64 while(for_i>=0) 65 { 66 if(new_set_par[for_i+1]<new_set_par[for_i])//当发现逆序时 67 { 68 if(reverse!=-1)//如果已经发现了逆序的对，则当前序列不可能是子序列根据一型操作生成的 69 { 70 free(new_set_par); 71 return 0;//所以直接返回 72 } 73 else 74 { 75 if(equal!=-1)//如果已经发现了相等的对，则当前序列也不可能通过一型操作生成 76 { 77 free(new_set_par); 78 return 0;//直接返回 79 } 80 else//否则，记录下当前的逆序索引 81 { 82 reverse=for_i; 83 } 84 } 85 } 86 else//当不是逆序时 87 { 88 if(new_set_par[for_i+1]==new_set_par[for_i])//如果发现的是相等的对 89 { 90 if(equal==-1)//如果之前木有发现相等的对 91 { 92 equal=for_i;//则直接赋值 93 } 94 //这样我们就记录了从右到左的第一个相等的对 95 } 96 } 97 for_i--;//遍历 98 } 99 if(reverse==-1)//最后如果逆序对不存在 100 { 101 if (equal != SET - 2) 102 { 103 new_set_par[equal + 1]++;//直接对相等的那个对后面的那个数加一 104 } 105 else//如果最后一对是相等的，则不可能是通过第一个操作生成的 106 { 107 free(new_set_par); 108 return 0; 109 } 110 } 111 else//如果逆序对存在 112 { 113 if(new_set_par[reverse+1]+1<new_set_par[reverse])//如果这个逆序的差值大于1，则不可能由一型操作生成 114 { 115 free(new_set_par); 116 return 0; 117 } 118 else//如果相差刚好为1，我们还需要考虑后面的那个数是否比逆序对后面的那个数刚好大一 119 { 120 if (new_set_par[reverse + 2] == new_set_par[reverse]) 121 { 122 new_set_par[reverse + 1]++; 123 } 124 else 125 { 126 free(new_set_par); 127 return 0; 128 } 129 } 130 } 131 insert_new_set_par(new_set_par); 132 return 1; 133 } 134 int type_two(int* father_set_par) 135 { 136 int for_i,temp,for_j,for_k,for_m; 137 int* new_set_par; 138 int* second_new_set_par; 139 new_set_par = (int*) malloc(sizeof(int) *SET); 140 for (for_i = 0; for_i < SET; for_i++) 141 { 142 new_set_par[for_i] = father_set_par[for_i]; 143 } 144 for_i = SET - 2; 145 while( (new_set_par[for_i] <=new_set_par[for_i + 1])&&for_i>=0)//寻找从右边开始的第一个逆序对 146 { 147 for_i--; 148 }//这里由限制生长的性质，从右数第一个逆序对不可能是开头的第一个对 149 //下面来讨论的是第二个操作没有生成新逆序对的情况 150 //我们需要扫描每一个在for_i右边的增序对，并考虑他的可行性 151 for_j = SET - 2; 152 while (for_j > for_i)//遍历 153 { 154 if (new_set_par[for_j] < new_set_par[for_j + 1])//增序对 155 { 156 for_k = for_j - 1; 157 while( (new_set_par[for_k] < new_set_par[for_j])&&for_k>=0) 158 { 159 for_k--; 160 } 161 if (for_k != -1)//如果当前值并不比前面所有的值都大，则交换之后遵守k限制增长规则 162 { 163 second_new_set_par = (int*) malloc(sizeof(int) *SET);//这里我们要建立副本，因为可能会有多个 164 for (for_m = 0; for_m < SET; for_m++) 165 { 166 second_new_set_par[for_m] = new_set_par[for_m]; 167 } 168 //然后进行调换 169 temp = second_new_set_par[for_j + 1]; 170 second_new_set_par[for_j + 1] = second_new_set_par[for_j]; 171 second_new_set_par[for_j] = temp; 172 insert_new_set_par(second_new_set_par); 173 } 174 else//如果当前值比之前的都大，都不可能是通过第二种操作生成的。例子，11123不可以由11132生成，因为 175 //后者违反了k生长的规则 176 { 177 //do nothing 178 }//其实这里的判断可以合并起来 179 } 180 else 181 { 182 //do nothing 183 } 184 for_j--; 185 } 186 if (for_i != -1)//此时对应的是生成的父节点有逆序对的情况 187 { 188 if (new_set_par[for_i - 1] <= new_set_par[for_i + 1])//对应的是二型操作生成了新逆序对的情况 189 { 190 for_k = for_j - 2; 191 while (for_k >= 0 && (new_set_par[for_k] < new_set_par[for_j - 1])) 192 { 193 for_k--; 194 }//同样需要考虑当前值和前一个值都是第一次出现的情况，这种情况下是不合法的 195 if (for_k == -1)//例子11232不可以由11322生成，因为后者不是k限制生长的。 196 { 197 free(new_set_par); 198 return 0; 199 } 200 second_new_set_par = (int*) malloc(sizeof(int) *SET);//这里我们要建立副本，因为可能会有多个 201 for (for_m = 0; for_m < SET; for_m++) 202 { 203 second_new_set_par[for_m] = new_set_par[for_m]; 204 } 205 //然后进行调换 206 temp = second_new_set_par[for_i - 1]; 207 second_new_set_par[for_i -1] = second_new_set_par[for_i]; 208 second_new_set_par[for_i] = temp; 209 insert_new_set_par(second_new_set_par); 210 }//逆向操作交换一下就可以了 211 else 212 { 213 //do nothing 214 } 215 } 216 else 217 { 218 //do nothing 因为其他的留给下面的过程去考虑 219 } 220 free(new_set_par); 221 return 0; 222 } 223 224 225 int main() 226 { 227 int for_i,for_j; 228 struct set_par_link* temp_set_par_link; 229 standard_set_par = (int*) malloc(sizeof(int) *SET); 230 for(for_i=0;for_i<SET-PART;for_i++) 231 { 232 standard_set_par[for_i]=1; 233 } 234 for(for_j=1;for_j<=PART;for_j++) 235 { 236 standard_set_par[for_i+for_j-1]=for_j; 237 } 238 insert_new_set_par(standard_set_par);//插入第一个节点，即头节点 239 while (set_par_link_head != NULL)//然后开始进行层序遍历 240 { 241 type_two(set_par_link_head->new_set); 242 type_one(set_par_link_head->new_set); 243 temp_set_par_link = set_par_link_head->next_set_par; 244 output(set_par_link_head->new_set); 245 free(set_par_link_head->new_set); 246 free(set_par_link_head); 247 set_par_link_head = temp_set_par_link; 248 } 249 }