学步园

1. 增量构造

#include <iostream><br /> using namespace std;<br /> #define N 1001<br /> int rcd[N];<br /> int used[N];<br /> int num[N];<br /> int n;<br /> void subset(int l)<br /> {<br /> for(int i = 0; i < l; i++)<br /> {<br /> cout << rcd[i] << " ";<br /> }<br /> cout << endl;<br /> int s = l ? rcd[l-1]+1 : 0;<br /> for(int i = s; i < n; i++)<br /> {<br /> rcd[l] = i;<br /> subset(l + 1);<br /> }<br /> }<br /> int readData()<br /> {<br /> int i;<br /> if( scanf("%d", &n) == EOF)<br /> {<br /> return 0;<br /> }<br /> for(int i = 0; i < n; i++) scanf("%d", &num[i]);<br /> for(int i = 0; i < n; i++) used[i] = 0;<br /> return 1;<br /> }<br /> int main()<br /> {<br /> while(readData())<br /> {<br /> subset(0);<br /> }<br /> }

2.  位向量法

#include <iostream><br /> using namespace std;<br /> #define N 1001<br /> int rcd[N];<br /> int used[N];<br /> int num[N];<br /> int n;<br /> void subset(int l)<br /> {<br /> if(l == n)<br /> {<br /> for(int i = 0; i < n; i++)<br /> {<br /> if(used[i])<br /> {<br /> cout << num[i] << " ";<br /> }<br /> }<br /> cout << endl;<br /> }<br /> else<br /> {<br /> used[l] = 1;<br /> subset(l + 1);<br /> used[l] = 0;<br /> subset(l + 1);<br /> }<br /> }<br /> int readData()<br /> {<br /> int i;<br /> if( scanf("%d", &n) == EOF)<br /> {<br /> return 0;<br /> }<br /> for(int i = 0; i < n; i++) scanf("%d", &num[i]);<br /> for(int i = 0; i < n; i++) used[i] = 0;<br /> return 1;<br /> }<br /> int main()<br /> {<br /> while(readData())<br /> {<br /> subset(0);<br /> }<br /> }

3. 一般组合

#include <iostream><br /> using namespace std;<br /> #define N 1001<br /> int rcd[N];<br /> int num[N];<br /> int n;<br /> int m;<br /> void selectCombination(int l, int p)<br /> {<br /> if(l == m)<br /> {<br /> for(int i = 0; i < m; i++)<br /> {<br /> cout << rcd[i] << " ";<br /> }<br /> cout << endl;<br /> }<br /> else<br /> {<br /> for(int i = p; i < n; i++)<br /> {<br /> rcd[l] = num[i];<br /> selectCombination(l+1, i+1);<br /> }<br /> }<br /> }<br /> int readData()<br /> {<br /> int i;<br /> if( scanf("%d%d", &n, &m) == EOF)<br /> {<br /> return 0;<br /> }<br /> for(int i = 0; i < n; i++) scanf("%d", &num[i]);<br /> return 1;<br /> }<br /> int main()<br /> {<br /> while(readData())<br /> {<br /> selectCombination(0, 0);<br /> }<br /> }

4. 全组合

#include <iostream><br /> using namespace std;<br /> #define N 1001<br /> int rcd[N];<br /> int num[N];<br /> int n;<br /> void fullCombination(int l, int p)<br /> {<br /> for(int i = 0; i < l; i++)<br /> {<br /> cout << rcd[i] << " ";<br /> }<br /> cout << endl;<br /> for(int i = p; i < n; i++)<br /> {<br /> rcd[l] = num[i];<br /> fullCombination(l+1, i+1);<br /> }<br /> }<br /> int readData()<br /> {<br /> int i;<br /> if( scanf("%d", &n) == EOF)<br /> {<br /> return 0;<br /> }<br /> for(int i = 0; i < n; i++) scanf("%d", &num[i]);<br /> return 1;<br /> }<br /> int main()<br /> {<br /> while(readData())<br /> {<br /> fullCombination(0, 0);<br /> }<br /> }

5. 去除重复组合

#include <iostream><br /> using namespace std;<br /> #define N 1001<br /> int rcd[N];<br /> int num[N];<br /> int used[N];<br /> int n;<br /> int m;<br /> void unrepeatFullCombination(int l, int p)<br /> {<br /> for(int i = 0; i < l; i++)<br /> {<br /> cout << rcd[i] << " ";<br /> }<br /> cout << endl;<br /> for(int i = p; i < m; i++)<br /> {<br /> if(used[i] > 0)<br /> {<br /> used[i]--;<br /> rcd[l] = num[i];<br /> unrepeatFullCombination(l+1, i);<br /> used[i]++;<br /> }<br /> }<br /> }<br /> int readData()<br /> {<br /> int i, j;<br /> if( scanf("%d", &n) == EOF)<br /> {<br /> return 0;<br /> }<br /> int val;<br /> for(i = 0; i < n; i++)<br /> {<br /> scanf("%d", &val);<br /> for(j = 0; j < m; j++)<br /> {<br /> if(num[j] == val)<br /> {<br /> used[j]++;<br /> break;<br /> }<br /> }<br /> if(j == m)<br /> {<br /> num[m] = val;<br /> used[m++] = 1;<br /> }<br /> }<br /> return 1;<br /> }<br /> int main()<br /> {<br /> while(readData())<br /> {<br /> unrepeatFullCombination(0, 0);<br /> }<br /> }

测试结果：

/home/a/j/nomad2:cat input |./a.out<br /> 1<br /> 1 1<br /> 1 1 3<br /> 1 3<br /> 3