Code with comments

05.10.2021

Multithreading • Combinatorics • Direct product

Consider an algorithm for obtaining a Cartesian product using Java Streams. This solution is similar to three nested for loops, with the difference that the outer loop is replaced with a stream for the convenience of subsequent parallelization. We’ll use the reduce method with three parameters: identity, accumulator and combiner.

In parallel mode, the speed of the algorithm increases when multiplying a large number of small lists, for example, 20 lists of 2 elements or 15 lists of 3 elements. The computation time reduces by one and a half to two times. In other cases, the computation time is about the same as for three nested for loops.

22.09.2021

Combinations of sequence elements

Combinatorics • Arrangements • Permutations

Consider a problem where you need to get all possible combinations of sequence elements, in which the number of elements in the combination does not exceed a given maximum, and let’s write a method for solving in Java with the appropriate filter for the minimum and maximum number of elements.

An arrangement is an ordered set of {k} distinct elements from a set of {n} distinct elements, where {k ≤ n}. If {k = n}, then this ordered set is a permutation. For the universality of the solution, we’ll also consider permutations as a special case of arrangement.

14.09.2021

Combinations of elements by columns

Combinatorics • Direct product

In a two-dimensional array, data is stored row-wise. Consider an algorithm for obtaining a Cartesian product by columns using three nested loops. The number of rows and columns can be arbitrary. We multiply the columns of the table sequentially and accumulate the result. The values do not necessarily have to be populated — we discard the null elements.

10.09.2021

Pascal's Triangle in Java

Two-dimensional array • Binomial coefficients

Consider a variant of the implementation of Pascal’s triangle in Java. For the simplicity of storing and processing data, we represent the triangle as a two-dimensional array, in which the elements of the first row and column are equal to one, and all other elements are the sum of the two previous elements in the row and column.

07.09.2021

Cartesian product of sets

Combinatorics • Direct product

Consider an algorithm for obtaining a Cartesian product of multiple sets using three nested loops. The number of sets and their elements can be arbitrary. We multiply the sets sequentially and accumulate the result. The order does not matter, since the product does not change due to the permutation of the multipliers. As a result, the order will be different, but the combinations will be the same.