Skip to content

Commit 7b3da02

Browse files
chandra1123chandra1123
committed
BAEL-2504 Combinations
Initial Combinations code.
1 parent 9f30be5 commit 7b3da02

8 files changed

Lines changed: 209 additions & 0 deletions

File tree

‎algorithms-miscellaneous-1/pom.xml‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -39,6 +39,11 @@
3939
<version>${org.assertj.core.version}</version>
4040
<scope>test</scope>
4141
</dependency>
42+
<dependency>
43+
<groupId>com.github.dpaukov</groupId>
44+
<artifactId>combinatoricslib3</artifactId>
45+
<version>3.3.0</version>
46+
</dependency>
4247
</dependencies>
4348

4449
<build>

‎algorithms-miscellaneous-1/src/main/java/com/baeldung/algorithms/combination/ApacheCommonsCombinationGenerator.java‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
package com.baeldung.algorithms.combination;
2+
3+
import java.util.Arrays;
4+
import java.util.Iterator;
5+
6+
import org.apache.commons.math3.util.CombinatoricsUtils;
7+
8+
public class ApacheCommonsCombinationGenerator {
9+
10+
public static void main(String[] args) {
11+
Iterator<int[]> iterator = CombinatoricsUtils.combinationsIterator(5, 3);
12+
while (iterator.hasNext()) {
13+
final int[] combination = iterator.next();
14+
System.out.println(Arrays.toString(combination));
15+
}
16+
}
17+
}

‎algorithms-miscellaneous-1/src/main/java/com/baeldung/algorithms/combination/CombinatoricsLibCombinationGenerator.java‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package com.baeldung.algorithms.combination;
2+
3+
import org.paukov.combinatorics3.Generator;
4+
5+
public class CombinatoricsLibCombinationGenerator {
6+
7+
public static void main(String[] args) {
8+
Generator.combination(0, 1, 2, 3, 4, 5)
9+
.simple(3)
10+
.stream()
11+
.forEach(System.out::println);
12+
}
13+
}

‎algorithms-miscellaneous-1/src/main/java/com/baeldung/algorithms/combination/GuavaCombinationsGenerator.java‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
package com.baeldung.algorithms.combination;
2+
3+
import java.util.Arrays;
4+
import java.util.Set;
5+
6+
import com.google.common.collect.ImmutableSet;
7+
import com.google.common.collect.Sets;
8+
9+
public class GuavaCombinationsGenerator {
10+
11+
public static void main(String[] args) {
12+
13+
Set<Set<Integer>> combinations = Sets.combinations(ImmutableSet.of(0, 1, 2, 3, 4, 5), 3);
14+
System.out.println(combinations.size());
15+
System.out.println(Arrays.toString(combinations.toArray()));
16+
}
17+
}

‎algorithms-miscellaneous-1/src/main/java/com/baeldung/algorithms/combination/IterativeCombinationGenerator.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.baeldung.algorithms.combination;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
public class IterativeCombinationGenerator {
8+
9+
private static final int N = 5;
10+
private static final int R = 2;
11+
12+
public List<int[]> generate(int n, int r) {
13+
List<int[]> combinations = new ArrayList<>();
14+
int[] combination = new int[r];
15+
16+
for (int i = 0; i < r; i++) {
17+
combination[i] = i;
18+
}
19+
20+
while (combination[r - 1] < n) {
21+
combinations.add(combination.clone());
22+
23+
int t = r - 1;
24+
while (t != 0 && combination[t] == n - r + t) {
25+
t--;
26+
}
27+
combination[t]++;
28+
for (int i = t + 1; i < r; i++) {
29+
combination[i] = combination[i - 1] + 1;
30+
}
31+
}
32+
33+
return combinations;
34+
}
35+
36+
public static void main(String[] args) {
37+
IterativeCombinationGenerator generator = new IterativeCombinationGenerator();
38+
List<int[]> combinations = generator.generate(N, R);
39+
System.out.println(combinations.size());
40+
for (int[] combination : combinations) {
41+
System.out.println(Arrays.toString(combination));
42+
}
43+
}
44+
45+
}

‎algorithms-miscellaneous-1/src/main/java/com/baeldung/algorithms/combination/SelectionRecursiveCombinationGenerator.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package com.baeldung.algorithms.combination;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
public class SelectionRecursiveCombinationGenerator {
8+
9+
private static final int N = 6;
10+
private static final int R = 3;
11+
12+
public List<int[]> generate(int n, int r) {
13+
List<int[]> combinations = new ArrayList<>();
14+
helper(combinations, new int[r], 0, n - 1, 0);
15+
return combinations;
16+
}
17+
18+
private void helper(List<int[]> combinations, int data[], int start, int end, int index) {
19+
if (index == data.length) {
20+
int[] combination = data.clone();
21+
combinations.add(combination);
22+
} else {
23+
int max = Math.min(end, end + 1 - data.length + index);
24+
for (int i = start; i <= max; i++) {
25+
data[index] = i;
26+
helper(combinations, data, i + 1, end, index + 1);
27+
}
28+
}
29+
}
30+
31+
public static void main(String[] args) {
32+
SelectionRecursiveCombinationGenerator generator = new SelectionRecursiveCombinationGenerator();
33+
List<int[]> combinations = generator.generate(N, R);
34+
System.out.println(combinations.size());
35+
for (int[] combination : combinations) {
36+
System.out.println(Arrays.toString(combination));
37+
}
38+
}
39+
}

‎algorithms-miscellaneous-1/src/main/java/com/baeldung/algorithms/combination/SetRecursiveCombinationGenerator.java‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.baeldung.algorithms.combination;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
public class SetRecursiveCombinationGenerator {
8+
9+
private static final int N = 6;
10+
private static final int R = 3;
11+
12+
public List<int[]> generate(int n, int r) {
13+
List<int[]> combinations = new ArrayList<>();
14+
helper(combinations, new int[r], 0, n - 1, 0, r);
15+
return combinations;
16+
}
17+
18+
private void helper(List<int[]> combinations, int data[], int start, int end, int index, int r) {
19+
if (index == data.length) {
20+
int[] combination = data.clone();
21+
combinations.add(combination);
22+
23+
} else if (start <= end) {
24+
data[index] = start;
25+
helper(combinations, data, start + 1, end, index + 1, r);
26+
helper(combinations, data, start + 1, end, index, r);
27+
}
28+
}
29+
30+
public static void main(String[] args) {
31+
SetRecursiveCombinationGenerator generator = new SetRecursiveCombinationGenerator();
32+
List<int[]> combinations = generator.generate(N, R);
33+
System.out.println(combinations.size());
34+
for (int[] combination : combinations) {
35+
System.out.println(Arrays.toString(combination));
36+
}
37+
}
38+
}

‎algorithms-miscellaneous-1/src/test/java/com/baeldung/algorithms/combination/CombinationUnitTest.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package com.baeldung.algorithms.combination;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
5+
import java.util.List;
6+
7+
import org.junit.Test;
8+
9+
public class CombinationUnitTest {
10+
11+
private static final int N = 5;
12+
private static final int R = 3;
13+
private static final int nCr = 10;
14+
15+
@Test
16+
public void givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount() {
17+
SetRecursiveCombinationGenerator generator = new SetRecursiveCombinationGenerator();
18+
List<int[]> selection = generator.generate(N, R);
19+
assertEquals(nCr, selection.size());
20+
}
21+
22+
@Test
23+
public void givenSetAndSelectionSize_whenCalculatedUsingSelectionRecursiveAlgorithm_thenExpectedCount() {
24+
SelectionRecursiveCombinationGenerator generator = new SelectionRecursiveCombinationGenerator();
25+
List<int[]> selection = generator.generate(N, R);
26+
assertEquals(nCr, selection.size());
27+
}
28+
29+
@Test
30+
public void givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount() {
31+
IterativeCombinationGenerator generator = new IterativeCombinationGenerator();
32+
List<int[]> selection = generator.generate(N, R);
33+
assertEquals(nCr, selection.size());
34+
}
35+
}

0 commit comments

Comments
 (0)