Порой программистам приходится сталкиваться с комбинаторикой для решения насущных задач. Мне на практике пришлось сделать «расстрел» фоторграфий. Нужно было сгенерировать все возможные размещения трех изображений пуль и наложить их поверх некой исходной картинки. Все сгенерированные изображения должны иметь прозрачный фон, иначе ничего хорошего из этого не получится. Привычным для меня языком программирования является Java, поэтому приведу пример того, как с помощью комбинаторики и Java написать небольшую программу, которая будет выполнять поставленную задачу.
Что такое сочетания в комбинаторике
В комбинаторике размещением из n по k называется упорядоченный набор k элементов, выбранных из данного множества, содержащего n различных элементов. (Wikipedia.org)
Для нашей задачи у нас имеется 3 картинки с изображениями пуль, размером 19 на 19 px и в формате PNG:
Требуется сгенерировать все возможные размещения этих изображений и наложить их поверх некой стартовой картинки, например:
И вот так будет выглядеть одно размещение из 19ти возможных:
Реализация алгоритма на Java
Весь код я приводить не буду, а приведу лишь ключевые концепции (код написан для примера, без учета code style и т.д.).
Пример генерации одного элемента на Java:
Пример генерации размещений для двух и трех элементов:
Функция generateImg() работает по тому же принципу, что и функция generateSingleImg() приведена на первом скриншоте, единственное различие — это высталение координат для 2ой и 3ей пуль.
Заключение и выводы
Использовать алгоритм размещений может быть очень полезно. Если вы сталкнетесь с задачей, где требуется сгенерировать различные размещения или вариации с повторениями — то данная статья может вам пригодиться.
Автор: diriusgigi
