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

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

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

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

Представим такую ситуацию: компания по продаже компьютеров хочет написать самую эффективную рассылку для своих клиентов. Маркетологи сказали, что в письме обязательно должно быть 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. Если на момент запуска рекурсии в этой переменной ничего не было — создаётся пустой массив.

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

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

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 элементов.

Что дальше

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

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Виталий Вебер

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства и компенсация, если вы пойдёте работать в «Яндекс».
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
medium