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

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

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

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

О чём речь

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

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

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

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

В чём идея

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

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

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

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

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

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

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

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

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

Алгоритм

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

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

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

var memo = memo || [];

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

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

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

var email = ['скидка', 'анонс', 'популярное', 'рассказ'];

// массив для результатов перестановок
var results = [];

// рекурсивная функция
// на вход получает текущий массив и массив с памятью предыдущих вычислений
function permute(arr, memo) {
  // переменная для хранения фрагмента массива
  var cur;

  // делаем переменную для хранения промежуточных результатов
  // в программировании это называется «мемоизация»
  var memo = memo || [];

  // какой размер входного массива — такой длины и делаем цикл, чтобы перебрать все элементы
  for (var i = 0; i < arr.length; i++) {

    // получаем новый массив cur, удаляя из входного массива один элемент, начиная с текущей позиции
    // при этом из входного массива этот элемент тоже удалится
    cur = arr.splice(i, 1);

    // если от входного массива ничего не осталось
    if (arr.length === 0) {
      // то приклеиваем текущее значение нарезки к варианту, который лежит в памяти, 
      // и добавляем получившийся результат в итоговый массив
      results.push(memo.concat(cur));
    }

    // вызываем новый виток рекурсии
    // в качестве аргументов передаём копию входящего массива и добавляем к кешу памяти то, что получилось после удаления одного символа из входящего массива
    permute(arr.slice(), memo.concat(cur));

    // возвращаем в исходный массив первый элемент из нового массива, но уже на другую позицию
    arr.splice(i, 0, cur[0]);
  }

  // возвращаем обратно массив с результатами перестановок
  return results;
}

permute(email);

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

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

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

Что дальше

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

Алгоритмы — основа разработки

Изучите алгоритмы, чтобы легко проходить ИТ-собеседования и делать более совершенный софт. Старт — бесплатно. После обучения — помощь с трудоустройством.

Новый уровень тут