-
Notifications
You must be signed in to change notification settings - Fork 5
/
SubSets.java
executable file
·72 lines (63 loc) · 1.91 KB
/
SubSets.java
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
package com.vee.algorithms.dynprog;
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import org.junit.Test;
public class SubSets {
public Set<List<String>> powerSetNormal(List<String> list) {
Set<List<String>> powerset = new LinkedHashSet<List<String>>();
powerset.add(new ArrayList<String>());
for (String s: list) {
Set<List<String>> subpowerset = new LinkedHashSet<List<String>>();
for (List<String> subset : powerset) {
List<String> newSubset = new ArrayList<String>(subset);
newSubset.add(s);
subpowerset.add(newSubset);
}
powerset.addAll(subpowerset);
}
return powerset;
}
public Set<List<String>> powerSetBinary(List<String> list) {
Set<List<String>> powerset = new LinkedHashSet<List<String>>();
for (int i = 0; i < (1 << list.size()); i++) {
String s = String.format("%"+list.size()+"s", Integer.toBinaryString(i)).replace(' ', '0');
List<String> newSubset = new ArrayList<String>();
for (int j = 0; j < s.length(); j++) {
if (s.charAt(j) == '1') {
newSubset.add(list.get(j));
}
}
powerset.add(newSubset);
}
return powerset;
}
public boolean subSetSumRecursion(int[] a, int sum) {
return false;
}
public boolean subSetSum2D(int[] a, int sum) {
return false;
}
public List<List<Integer>> subSetSum(int[] a, int sum) {
return new ArrayList<>();
}
//java -cp .:/usr/share/java/junit.jar org.junit.runner.JUnitCore [test class name]
@Test
public void testSubset() {
List<String> s= new ArrayList<String>();
int n = 10;
for (int i = 1; i <= n; i++) {
s.add(i+"");
}
long start = System.nanoTime();
powerSetBinary(s);
System.out.println(System.nanoTime() - start);
start = System.nanoTime();
Set<List<String>> powerset = powerSetNormal(s);
System.out.println(System.nanoTime() - start);
for (List<String> subset : powerset) {
System.out.println(subset);
}
}
}