Cartesian product in parallel streams
Multithreading • Combinatorics • Direct productConsider 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 • PermutationsConsider 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 productIn 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.
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.
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