Skip to content

Commit c69690d

Browse files
amit2103amit2103
committed
Merge branch 'master' of https://github.com/eugenp/tutorials into BAEL-12185
2 parents f9ce72f + 3a57c59 commit c69690d

151 files changed

Lines changed: 3232 additions & 336 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎algorithms-miscellaneous-1/pom.xml‎

Lines changed: 6 additions & 1 deletion
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>
@@ -77,7 +82,7 @@
7782
<commons-math3.version>3.6.1</commons-math3.version>
7883
<org.assertj.core.version>3.9.0</org.assertj.core.version>
7984
<commons-codec.version>1.11</commons-codec.version>
80-
<guava.version>25.1-jre</guava.version>
85+
<guava.version>27.0.1-jre</guava.version>
8186
</properties>
8287

8388
</project>

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

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
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+
private static final int N = 6;
11+
private static final int R = 3;
12+
13+
/**
14+
* Print all combinations of r elements from a set
15+
* @param n - number of elements in set
16+
* @param r - number of elements in selection
17+
*/
18+
public static void generate(int n, int r) {
19+
Iterator<int[]> iterator = CombinatoricsUtils.combinationsIterator(n, r);
20+
while (iterator.hasNext()) {
21+
final int[] combination = iterator.next();
22+
System.out.println(Arrays.toString(combination));
23+
}
24+
}
25+
26+
public static void main(String[] args) {
27+
generate(N, R);
28+
}
29+
}

‎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: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
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+
/**
13+
* Generate all combinations of r elements from a set
14+
* @param n the number of elements in input set
15+
* @param r the number of elements in a combination
16+
* @return the list containing all combinations
17+
*/
18+
public List<int[]> generate(int n, int r) {
19+
List<int[]> combinations = new ArrayList<>();
20+
int[] combination = new int[r];
21+
22+
// initialize with lowest lexicographic combination
23+
for (int i = 0; i < r; i++) {
24+
combination[i] = i;
25+
}
26+
27+
while (combination[r - 1] < n) {
28+
combinations.add(combination.clone());
29+
30+
// generate next combination in lexicographic order
31+
int t = r - 1;
32+
while (t != 0 && combination[t] == n - r + t) {
33+
t--;
34+
}
35+
combination[t]++;
36+
for (int i = t + 1; i < r; i++) {
37+
combination[i] = combination[i - 1] + 1;
38+
}
39+
}
40+
41+
return combinations;
42+
}
43+
44+
public static void main(String[] args) {
45+
IterativeCombinationGenerator generator = new IterativeCombinationGenerator();
46+
List<int[]> combinations = generator.generate(N, R);
47+
System.out.println(combinations.size());
48+
for (int[] combination : combinations) {
49+
System.out.println(Arrays.toString(combination));
50+
}
51+
}
52+
}

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

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
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+
/**
13+
* Generate all combinations of r elements from a set
14+
* @param n - number of elements in input set
15+
* @param r - number of elements to be chosen
16+
* @return the list containing all combinations
17+
*/
18+
public List<int[]> generate(int n, int r) {
19+
List<int[]> combinations = new ArrayList<>();
20+
helper(combinations, new int[r], 0, n - 1, 0);
21+
return combinations;
22+
}
23+
24+
/**
25+
* Choose elements from set by recursing over elements selected
26+
* @param combinations - List to store generated combinations
27+
* @param data - current combination
28+
* @param start - starting element of remaining set
29+
* @param end - last element of remaining set
30+
* @param index - number of elements chosen so far.
31+
*/
32+
private void helper(List<int[]> combinations, int data[], int start, int end, int index) {
33+
if (index == data.length) {
34+
int[] combination = data.clone();
35+
combinations.add(combination);
36+
} else {
37+
int max = Math.min(end, end + 1 - data.length + index);
38+
for (int i = start; i <= max; i++) {
39+
data[index] = i;
40+
helper(combinations, data, i + 1, end, index + 1);
41+
}
42+
}
43+
}
44+
45+
public static void main(String[] args) {
46+
SelectionRecursiveCombinationGenerator generator = new SelectionRecursiveCombinationGenerator();
47+
List<int[]> combinations = generator.generate(N, R);
48+
for (int[] combination : combinations) {
49+
System.out.println(Arrays.toString(combination));
50+
}
51+
System.out.printf("generated %d combinations of %d items from %d ", combinations.size(), R, N);
52+
}
53+
}

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

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
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 = 5;
10+
private static final int R = 2;
11+
12+
/**
13+
* Generate all combinations of r elements from a set
14+
* @param n - number of elements in set
15+
* @param r - number of elements in selection
16+
* @return the list containing all combinations
17+
*/
18+
public List<int[]> generate(int n, int r) {
19+
List<int[]> combinations = new ArrayList<>();
20+
helper(combinations, new int[r], 0, n-1, 0);
21+
return combinations;
22+
}
23+
24+
/**
25+
* @param combinations - List to contain the generated combinations
26+
* @param data - List of elements in the selection
27+
* @param start - index of the starting element in the remaining set
28+
* @param end - index of the last element in the set
29+
* @param index - number of elements selected so far
30+
*/
31+
private void helper(List<int[]> combinations, int data[], int start, int end, int index) {
32+
if (index == data.length) {
33+
int[] combination = data.clone();
34+
combinations.add(combination);
35+
} else if (start <= end) {
36+
data[index] = start;
37+
helper(combinations, data, start + 1, end, index + 1);
38+
helper(combinations, data, start + 1, end, index);
39+
}
40+
}
41+
42+
public static void main(String[] args) {
43+
SetRecursiveCombinationGenerator generator = new SetRecursiveCombinationGenerator();
44+
List<int[]> combinations = generator.generate(N, R);
45+
for (int[] combination : combinations) {
46+
System.out.println(Arrays.toString(combination));
47+
}
48+
System.out.printf("generated %d combinations of %d items from %d ", combinations.size(), R, N);
49+
}
50+
}

‎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+
}

‎algorithms-miscellaneous-2/src/main/java/com/baeldung/algorithms/reversingtree/TreeNode.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.baeldung.algorithms.reversingtree;
2+
3+
public class TreeNode {
4+
5+
private int value;
6+
private TreeNode rightChild;
7+
private TreeNode leftChild;
8+
9+
public int getValue() {
10+
return value;
11+
}
12+
13+
public void setValue(int value) {
14+
this.value = value;
15+
}
16+
17+
public TreeNode getRightChild() {
18+
return rightChild;
19+
}
20+
21+
public void setRightChild(TreeNode rightChild) {
22+
this.rightChild = rightChild;
23+
}
24+
25+
public TreeNode getLeftChild() {
26+
return leftChild;
27+
}
28+
29+
public void setLeftChild(TreeNode leftChild) {
30+
this.leftChild = leftChild;
31+
}
32+
33+
public TreeNode(int value, TreeNode rightChild, TreeNode leftChild) {
34+
this.value = value;
35+
this.rightChild = rightChild;
36+
this.leftChild = leftChild;
37+
}
38+
39+
public TreeNode(int value) {
40+
this.value = value;
41+
}
42+
}

‎algorithms-miscellaneous-2/src/main/java/com/baeldung/algorithms/reversingtree/TreeReverser.java‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package com.baeldung.algorithms.reversingtree;
2+
3+
import java.util.LinkedList;
4+
5+
public class TreeReverser {
6+
7+
public TreeNode createBinaryTree() {
8+
9+
TreeNode leaf1 = new TreeNode(3);
10+
TreeNode leaf2 = new TreeNode(1);
11+
TreeNode leaf3 = new TreeNode(9);
12+
TreeNode leaf4 = new TreeNode(6);
13+
14+
TreeNode nodeLeft = new TreeNode(2, leaf1, leaf2);
15+
TreeNode nodeRight = new TreeNode(7, leaf3, leaf4);
16+
17+
TreeNode root = new TreeNode(4, nodeRight, nodeLeft);
18+
19+
return root;
20+
}
21+
22+
public void reverseRecursive(TreeNode treeNode) {
23+
if (treeNode == null) {
24+
return;
25+
}
26+
27+
TreeNode temp = treeNode.getLeftChild();
28+
treeNode.setLeftChild(treeNode.getRightChild());
29+
treeNode.setRightChild(temp);
30+
31+
reverseRecursive(treeNode.getLeftChild());
32+
reverseRecursive(treeNode.getRightChild());
33+
}
34+
35+
public void reverseIterative(TreeNode treeNode) {
36+
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
37+
38+
if (treeNode != null) {
39+
queue.add(treeNode);
40+
}
41+
42+
while (!queue.isEmpty()) {
43+
44+
TreeNode node = queue.poll();
45+
if (node.getLeftChild() != null)
46+
queue.add(node.getLeftChild());
47+
if (node.getRightChild() != null)
48+
queue.add(node.getRightChild());
49+
50+
TreeNode temp = node.getLeftChild();
51+
node.setLeftChild(node.getRightChild());
52+
node.setRightChild(temp);
53+
}
54+
}
55+
56+
public String toString(TreeNode root) {
57+
if (root == null) {
58+
return "";
59+
}
60+
61+
StringBuffer buffer = new StringBuffer(String.valueOf(root.getValue())).append(" ");
62+
63+
buffer.append(toString(root.getLeftChild()));
64+
buffer.append(toString(root.getRightChild()));
65+
66+
return buffer.toString();
67+
}
68+
}

0 commit comments

Comments
 (0)