产生可能的集合
给定一组数字或符号，产生所有可能的集合（包括空集合），例如给定1 2 3，则可能的集合为：{}、{1}、{1,2}、{1,2,3}、{1,3}、{2}、{2,3}、{3}。
如果不考虑字典顺序，则有个简单的方法可以产生所有的集合，思考二进位数字加法，并注意1出现的位置，如果每个位置都对应一个数字，则由1所对应的数字所产生的就是一个集合，例如：
|
|
| 000 |
{} |
| 001 |
{3} |
| 010 |
{2} |
| 011 |
{2,3} |
| 100 |
{1} |
| 101 |
{1,3} |
| 110 |
{1,2} |
| 111 |
{1,2,3} |
瞭解这个方法之后，剩下的就是如何产生二进位数？有许多方法可以使用，您可以使用unsigned型别加上&位元运算来产生，这边则是使用阵列搜 寻，首先阵列内容全为0，找第一个1，在还没找到之前将走访过的内容变为0，而第一个找到的0则变为 1，如此重複直到所有的阵列元素都变为1为止，例如：
000 => 100 => 010 => 110 => 001 => 101 => 011 => 111
如果要产生字典顺序，例如若有4个元素，则：
{} => {1} => {1,2} => {1,2,3} => {1,2,3,4} =>
{1,2,4} =>
{1,3} => {1,3,4} =>
{1,4} =>
{2} => {2,3} => {2,3,4} =>
{2,4} =>
{3} => {3,4} =>
{4}
简单的说，如果有n个元素要产生可能的集合，当依序产生集合时，如果最后一个元素是n，而倒数第二个元素是m的话，例如：
{a b c d e n}
则下一个集合就是{a b c d e+1}，再依序加入后续的元素。
例如有四个元素，而当产生{1 2 3 4}集合时，则下一个集合就是{1 2 3+1}，也就是{1 2 4}，由于最后一个元素还是4，所以下一个集合就是{1 2+1}，也就是{1 3}，接下来再加入后续元素4，也就是{1 3 4}，由于又遇到元素4，所以下一个集合是{1 3+1}，也就是{1 4}。
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
|
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
int main(void) {
char digit[MAXSIZE];
int i, j;
int n;
printf("输入集合个数：");
scanf("%d", &n);
for(i = 0; i < n; i++)
digit[i] = '0';
printf("\n{}"); // 空集合
while(1) {
// 找第一个0，并将找到前所经过的元素变为0
for(i = 0; i < n && digit[i] == '1'; digit[i] = '0', i++);
if(i == n) // 找不到0
break;
else // 将第一个找到的0变为1
digit[i] = '1';
// 找第一个1，并记录对应位置
for(i = 0; i < n && digit[i] == '0'; i++);
printf("\n{%d", i+1);
for(j = i + 1; j < n; j++)
if(digit[j] == '1')
printf(",%d", j + 1);
printf("}");
}
printf("\n");
return 0;
}
|
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
|
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
int main(void) {
int set[MAXSIZE];
int i, n, position = 0;
printf("输入集合个数：");
scanf("%d", &n);
printf("\n{}");
set[position] = 1;
while(1) {
printf("\n{%d", set[0]); // 印第一个数
for(i = 1; i <= position; i++)
printf(",%d", set[i]);
printf("}");
if(set[position] < n) { // 递增集合个数
set[position+1] = set[position] + 1;
position++;
}
else if(position != 0) { // 如果不是第一个位置
position--; // 倒退
set[position]++; // 下一个集合尾数
}
else // 已倒退至第一个位置
break;
}
printf("\n");
return 0;
}
|
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
|
public class PossibleSet {
public static void main(String[] args) {
char[] digit = new char[4];
for(int i = 0; i < digit.length; i++)
digit[i] = '0';
System.out.println("{}"); // 空集合
while(true) {
// 找第一个0，并将找到前所经过的元素变为0
int i;
for(i = 0; i < digit.length && digit[i] == '1';
digit[i] = '0', i++);
if(i == digit.length) // 找不到0
break;
else // 将第一个找到的0变为1
digit[i] = '1';
// 找第一个1，并记录对应位置
for(i = 0; i < digit.length && digit[i] == '0'; i++);
System.out.print("{" + (i+1));
for(int j = i + 1; j < digit.length; j++)
if(digit[j] == '1')
System.out.print(", " + (j + 1));
System.out.println("}");
}
}
}
|
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
|
public class PossibleSet {
public static void main(String[] args) {
int[] set = new int[4];
int i, n, position = 0;
set[position] = 1;
while(true) {
System.out.print("{" + set[0]); // 印第一个数
for(i = 1; i <= position; i++)
System.out.print("," + set[i]);
System.out.print("}");
if(set[position] < set.length) { // 递增集合个数
set[position+1] = set[position] + 1;
position++;
}
else if(position != 0) { // 如果不是第一个位置
position--; // 倒退
set[position]++; // 下一个集合尾数
}
else // 已倒退至第一个位置
break;
}
System.out.println();
}
}
|
