-
Notifications
You must be signed in to change notification settings - Fork 105
Expand file tree
/
Copy pathallSubsets.java
More file actions
107 lines (90 loc) · 2.95 KB
/
allSubsets.java
File metadata and controls
107 lines (90 loc) · 2.95 KB
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import java.util.ArrayList;
import java.util.Arrays;
public class allSubsets{
public static void main(String[] args){
int[] a = {1,2,3};
ArrayList<ArrayList<Integer>> allsubsets = new ArrayList<ArrayList<Integer>>();
System.out.println("take subset:");
allsubsets = genSubsets(a, 0);
System.out.println(allsubsets.toString());
// gray code to generate all sets
System.out.println("gray code:");
boolean[] pick = new boolean[a.length];
//gray code
yarg(a, a.length, pick);
// move in/out
System.out.println("move in out:");
moveIn(a, a.length, new ArrayList<Integer>(), true);
}
public static void moveIn(int[] a, int k, ArrayList<Integer> t, boolean pick){
if (k == 0){
System.out.println(t.toString());
return;
}
moveIn(a, k-1, t, true);
if (pick){
t.add(a[k-1]);
//System.out.println("in " + a[k-1]);
}
else{
// remove object, not index,
// if int, it is taken as an index
t.remove((Object)a[k-1]);
//System.out.println("out " + a[k-1]);
}
moveIn(a, k-1, t, false);
}
public static ArrayList<ArrayList<Integer>> genSubsets(int[] a, int index){
ArrayList<ArrayList<Integer>> allsubsets;
if(a.length == index){
allsubsets = new ArrayList<ArrayList<Integer>>();
allsubsets.add( new ArrayList<Integer>());
}
else{
allsubsets = genSubsets(a, index+1);
int item = a[index];
ArrayList<ArrayList<Integer>> moresubsets = new ArrayList<ArrayList<Integer>>();
for(ArrayList<Integer> subset : allsubsets) {
ArrayList<Integer> newsubset = new ArrayList<Integer>();
newsubset.addAll(subset); //
newsubset.add(item);
moresubsets.add(newsubset);
}
allsubsets.addAll(moresubsets);
}
return allsubsets;
}
public static void show(boolean[] a, int[] n) {
ArrayList<Integer> tmp = new ArrayList<Integer>();
for (int i = 0; i < a.length; i++){
if (a[i] == true)
tmp.add(n[i]);
// gray code
/*
if (a[i] == true)
System.out.print(1);
else
System.out.print(0);
*/
}
System.out.println(tmp.toString());
}
public static void yarg(int[] n, int k, boolean[] a) {
if (k == 0) show(a, n);
else {
a[k-1] = true;
gray(n, k-1, a);
a[k-1] = false;
yarg(n, k-1, a);
}
}
public static void gray(int[] n, int k, boolean[] a) {
if (k == 0) show(a, n);
else {
a[k-1] = false;
gray(n, k-1, a);
a[k-1] = true;
yarg(n, k-1, a);
}
}
}