Мощь алгоритмов: автоматический поиск всех возможных комбинаций

Сдвигаем парадигму с помощью силы компьютеров

Это история об информатике, алгоритмах и понимании мощи компьютеров.

Представим такую ситуацию: компания по продаже компьютеров хочет написать самую эффективную рассылку для своих клиентов. Маркетологи сказали, что в письме обязательно должно быть 4 блока:

• предложение скидки;
• анонс новых товаров;
• блок с самыми популярными товарами;
• рассказ о том, почему нужно выбрать именно эту компанию.

Но никто не знал, в каком порядке лучше всего расположить эти блоки, чтобы рассылка сработала максимально круто. В итоге решили перебрать все комбинации и отправить много разных рассылок. Для этого позвали программиста, который написал для них простой скрипт — он выводит все варианты расположения блоков. Сегодня мы попробуем это повторить.

О чём речь

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

• Скидка → анонс → популярное → рассказ
• Рассказ → скидка → анонс → популярное
• Анонс → рассказ → скидка → популярное

Таких вариантов можно составить 4! («четыре факториал») — то есть 24 штуки. Восклицательный знак означает факториал, то есть нам нужно перемножить все числа от 1 до этого числа:

4! = 1 × 2 × 3 × 4 = 24

Получается, из четырёх блоков можно сделать 24 разных варианта письма. Вручную перебирать их все сложно, да и нет смысла: компьютер с этим справится гораздо быстрее. Для этого и сделаем алгоритм.

В чём идея

Чтобы перебрать все варианты, можно сделать так:

1. Смотрим, сколько у нас блоков — 4 штуки.
2. Делаем первый цикл.
3. Делаем второй цикл.
4. Делаем третий цикл.
5. Делаем четвёртый вложенный цикл.
6. Внутри этого перебираем все варианты и каждый раз проверяем, чтобы один блок не встречался два раза или больше.
7. Если условие выполняется — добавляем результат в итоговые варианты
8. На выходе получаем все варианты.

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

• про проверку на дубли;
• собирание всех последовательностей в какой-то новый массив;
• новые вложенные циклы и увеличение сложности условия, если блоков станет больше.

А можно подойти к вопросу иначе:

1. Берём массив с блоками.
2. Берём оттуда первый элемент, откладываем его в сторону и дальше пока работаем с оставшимся массивом.
3. В оставшемся массиве тоже берём первый элемент, откладываем его в сторону и снова работаем с оставшимся массивом.
4. Так погружаемся в массив до тех пор, пока в нём не останется ни одного элемента.
5. А теперь на каждом этапе возврата назад мы переставляем наш отложенный первый элемент на соседнее место и запоминаем получившуюся комбинацию.
6. Так на каждом шаге мы будем получать всё новые и новые комбинации перестановок — сначала это будут перестановки из двух элементов, потом из трёх и так далее.
7. Возвращаемся к пункту 2 и делаем то же самое со вторым элементом.
8. Так проходим все элементы до последнего.

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

На самом деле мы только что описали рекурсию: функцию, которая вызывает сама себя, но на каждом шаге с новыми условиями.

Почему рекурсия лучше вложенных циклов

Когда вложенных циклов мало, то с ними проще: можно контролировать всё вручную. А вот когда циклов становится не три, а 10 или 50, то сильно вырастает вероятность ошибиться в переменной или забыть про какое-то условие. В рекурсии такой проблемы нет: мы один раз описываем, как нырнуть и как оттуда вынырнуть, и всё, остальное компьютер сделает сам.

Ещё бывает такое, что мы заранее не знаем, сколько будет блоков для перестановок — 4 или 40, например. Рекурсия здесь тоже выигрывает: достаточно в одном цикле перебрать все элементы массива, а дальше всё сработает само.

Так и сделаем.

Алгоритм

Единственное, что нам понадобится нового для рекурсии, о чём мы ещё не говорили, — это мемоизация.

В программировании мемоизацией называют временное хранение промежуточных результатов вычислений, чтобы не вычислять их по сто раз. Один раз посчитал, добавил в переменную-кеш — и отлично.

В нашем случае за это будет отвечать такая строчка:

var memo = memo || [];

Она появляется в самом начале рекурсии и означает вот что:

1. Если в переменной memo уже что-то было — используется то, что было.
2. Если на момент запуска рекурсии в этой переменной ничего не было — создаётся пустой массив.

Так мы избавляемся от необходимости высчитывать промежуточные последовательности заново, а вместо этого используем временное хранилище.

Теперь смотрите код и читайте комментарии:

Запустим код в консоли браузера:

Видно, что мы получили 24 перестановки, как и должно было быть. Они все разные, ни в одной нет повторений — то, что нам нужно. Теперь можно отдать эти последовательности дальше, чтобы по каждой из них собрали своё письмо для клиентов.

Если интересно, как рекурсия справится со сложными вариантами и сколько их получится, — сделайте в исходном массиве в коде не 4, а 10 элементов.

Что дальше

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