Код с комментариями

04.10.2021

Декартово произведение в параллельных потоках

Многопоточность • Комбинаторика • Прямое произведение

Рассмотрим алгоритм получения декартова произведения с помощью потоков Java Stream. Это решение похоже на три вложенных цикла for с тем отличием, что здесь внешний цикл заменён на поток для удобства последующего распараллеливания. Будем использовать метод reduce с тремя параметрами: identity, accumulator и combiner.

В параллельном режиме скорость работы алгоритма увеличивается при перемножении большого количества маленьких списков, например 20 списков по 2 элемента или 15 списков по 3 элемента. Время вычислений уменьшается в полтора-два раза. В остальных случаях время работы примерно такое же, как у трёх вложенных циклов for.

20.09.2021

Комбинации элементов последовательности

Комбинаторика • Размещения • Перестановки

Рассмотрим задачу, в которой нужно получить все возможные комбинации элементов последовательности, где количество элементов в комбинации не превышает заданного максимума, и напишем метод для решения на Java с соответствующим отбором по минимальному и максимальному количеству элементов.

Размещением называется упорядоченный набор {k} различных элементов из множества {n} различных элементов, где {k ≤ n}. Если {k = n}, то такой упорядоченный набор называется перестановкой. Для универсальности решения перестановки тоже будем учитывать как частный случай размещения.

13.09.2021

Комбинации элементов по столбцам

Комбинаторика • Прямое произведение

В двухмерном массиве данные хранятся построчно. Рассмотрим алгоритм получения декартова произведения по столбцам с использованием трёх вложенных циклов. Количество строк и колонок может быть произвольным. Последовательно перемножаем колонки таблицы и накапливаем результат. Значения необязательно должны быть заполнены — нулевые элементы отбрасываем.

09.09.2021

Треугольник Паскаля на Java

Двухмерный массив • Биномиальные коэффициенты

Рассмотрим вариант реализации треугольника Паскаля на Java. Для простоты хранения и обработки данных представим треугольник в виде двухмерного массива, в котором элементы первой строки и колонки равны единице, а все остальные элементы — есть сумма двух предыдущих элементов в строке и в колонке.

06.09.2021

Декартово произведение множеств

Комбинаторика • Прямое произведение

Рассмотрим алгоритм получения декартова произведения нескольких множеств с использованием трёх вложенных циклов. Количество множеств и их элементов может быть произвольным. Последовательно перемножаем множества и накапливаем результат. Порядок значения не имеет, так как от перестановки множителей произведение не меняется. В результате порядок будет отличаться, но комбинации будут те же самые.