FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
java-algorithm-2010/allSubsets/src/allSubsets.java at master · xiaoningning/java-algorithm-2010 · GitHub
xiaoningning
java-algorithm-2010
Repository navigation
Code
Issues
Pull requests
1
(1)
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
java-algorithm-2010
/
allSubsets
/
src
/
allSubsets.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
107 lines (90 loc) · 2.95 KB
Breadcrumbs
java-algorithm-2010
/
allSubsets
/
src
/
allSubsets.java
Copy path
File metadata and controls
107 lines (90 loc) · 2.95 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
);
}
}
}
Back
|
FazBrowse Home
|
New Git URL