Problem solutions and solution descriptions

Cartesian product in parallel streams

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.

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*.

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.

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.

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.

© Golovin G.G., Code with comments, translation from Russian, 2024