本文章讨論的是将一個包含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("\n");
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("\n");
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 } ![牛客國慶集訓派對Day4 - G、I、H[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)