Как вернуть все комбинации из N бросков монеты с помощью рекурсии?

Запрос:

Используя JavaScript, напишите функцию, которая принимает целое число. Целое число представляет количество раз, когда монета подбрасывается. Используя только рекурсивные стратегии, верните массив, содержащий все возможные комбинации бросков монеты. Используйте H для представления орла и T для представления решки. Порядок комбинаций не имеет значения.

Например, передача 2 вернет: ["HH", "HT", "TH", "TT"]

Контекст:

Я относительно новичок в JavaScript, а также в концепции рекурсии. Это чисто для практики и понимания, поэтому решение не обязательно должно соответствовать направлению моего кода ниже; любые полезные методы или другие способы обдумывания этого полезны, если они чисто рекурсивны (без циклов).

Попытка:

Моя попытка сделать это началась с простого, однако действие постепенно становилось все более запутанным по мере того, как я увеличивал ввод. Я считаю, что это работает для входных данных 2, 3 и 4. Однако для входных данных 5 или выше отсутствуют комбинации в выходных данных. Спасибо заранее!

function coinFlips(num){
  const arr = [];
  let str = "";

  // adds base str ("H" * num)
  function loadStr(n) {
    if (n === 0) {
      arr.push(str);
      return traverseArr();
    }
    str += "H";
    loadStr(n - 1);
  }
  
  // declares start point, end point, and index to update within each str
  let start = 0;
  let end = 1;
  let i = 0;

  function traverseArr() {

    // base case
    if(i === str.length) {
      console.log(arr);
      return arr;
    }

    // updates i in base str to "T"
    // increments i
    // resets start and end
    if(end === str.length) {
      str = str.split('');
      str[i] = "T";
      str = str.join('');
      i++;
      start = i;
      end = i + 1;
      return traverseArr();
    }

    // action
    let tempStr = str.split('');
    tempStr[start] = "T";
    tempStr = tempStr.join('');
    if(!arr.includes(tempStr)){
      arr.push(tempStr);
    };
    tempStr = tempStr.split('');
    tempStr.reverse();
    tempStr = tempStr.join('');
    if(!arr.includes(tempStr)){
      arr.push(tempStr);
    };

    tempStr = str.split('');
    tempStr[end] = "T";
    tempStr = tempStr.join('');
    if(!arr.includes(tempStr)){
      arr.push(tempStr);
    };
    tempStr = tempStr.split('');
    tempStr.reverse();
    tempStr = tempStr.join('');
    if(!arr.includes(tempStr)){
      arr.push(tempStr);
    };

    tempStr = str.split('');
    tempStr[start] = "T";
    tempStr[end] = "T";
    tempStr = tempStr.join('');
    if(!arr.includes(tempStr)){
      arr.push(tempStr);
    };
    tempStr = tempStr.split('');
    tempStr.reverse();
    tempStr = tempStr.join('');
    if(!arr.includes(tempStr)){
      arr.push(tempStr);
    };

    // recursive case
    start++;
    end++;
    return traverseArr();
  }

  loadStr(num);
}

coinFlips(5);

javascript recursion combinations coin-flipping
person cj102    schedule 25.08.2020    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

const getFlips = (n) =>
  n <= 0
    ? ['']
    : getFlips (n - 1) .flatMap (r => [r + 'H', r + 'T'])

Определение нашего алгоритма

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

На каком значении мы повторяемся?

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

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

Когда заканчивается наша рекурсия?

Нам нужно прекратить повторяться в конце концов. Здесь мы могли бы остановиться, когда n равно 0 или, возможно, когда n равно 1. Оба варианта могут работать. Давайте на мгновение отложим это решение, чтобы посмотреть, что может быть проще.

Как нам преобразовать ответ с одного шага в ответ на следующий?

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

(Опять же, здесь возможны сложности для более сложных рекурсий. Например, нам может понадобиться использовать все нижние результаты для вычисления следующего значения. Например, найдите Каталонские номера. Здесь мы можем игнорировать это; наша рекурсия проста.)

Итак, как нам преобразовать, скажем, ['HH', 'HT', 'TH', 'TT'] в следующий шаг, ['HHH', 'HHT', 'HTH', 'HTT', 'THH', 'THT', 'TTH', 'TTT']? Хорошо, если мы внимательно посмотрим на следующий результат, мы увидим, что в первой половине все элементы начинаются с «H», а во второй — с «T». Если мы проигнорируем первые буквы, каждая половина будет копией нашего ввода, ['HH', 'HT', 'TH', 'TT']. Это выглядит очень многообещающе! Таким образом, наш рекурсивный шаг может состоять в том, чтобы сделать две копии предыдущего результата, первая с каждым значением, предшествующим 'H', вторая — с 'T'.

Каково значение для нашего базового случая?

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

Чтобы вернуться от ['HHH', 'HHT', 'HTH', 'HTT', 'THH', 'THT', 'TTH', 'TTT'] к ['HH', 'HT', 'TH', 'TT'], мы можем взять первую половину и удалить начальную букву «H» из каждого результата. Давай сделаем это снова. Из ['HH', 'HT', 'TH', 'TT'] мы берем первую половину и удаляем начальную букву «Н» из каждой, чтобы получить ['H', 'T']. Хотя это может быть нашей остановкой, что произойдет, если мы сделаем еще один шаг вперед? Взяв первую половину и удалив начальное H из одного оставшегося элемента, мы получим только ['']. Имеет ли этот ответ смысл? Я бы сказал, что да: сколько существует способов подбросить монету ноль раз? Только один. Как бы мы записали это как строку из Hs и Ts? Как пустая строка. Таким образом, массив, содержащий только пустую строку, является отличным ответом для случая 0. Это также отвечает на наш второй вопрос о том, когда заканчивается рекурсия. Он заканчивается, когда n равно нулю.

Написание кода для этого алгоритма

Конечно, теперь мы должны превратить этот алгоритм в код. Мы также можем сделать это в несколько шагов.

Объявление нашей функции

Мы пишем это, начиная с определения функции. Наш параметр называется n. Я собираюсь вызвать функцию getFlips. Итак, мы начинаем с

const getFlips = (n) =>
  <something here>

Добавляем наш базовый случай.

Мы уже говорили, что закончим, когда n будет равно нулю. Обычно я предпочитаю сделать это немного более устойчивым, проверяя любое n, которое меньше или равно нулю. Это остановит бесконечную рекурсию, если кто-то передаст отрицательное число. Вместо этого мы могли бы выбрать исключение в этом случае, но наше объяснение [''] для случая нуля, похоже, верно и для отрицательных значений. (Кроме того, я абсолютно ненавижу создание исключений!)

Это дает нам следующее:

const getFlips = (n) =>
  n <= 0
    ? ['']
    : <something here>

Здесь я решил использовать условное (троичное) выражение вместо операторов if-else, потому что я предпочитаю работать с выражениями, а не с операторами, насколько это возможно. Эту же технику можно легко написать с помощью if-else, если это кажется вам более естественным.

Обработка рекурсивного случая

Наше описание состояло в том, чтобы сделать две копии предыдущего результата, первая с каждым значением, предшествующим 'H', вторая — с 'T'. Наш предыдущий результат, конечно же, getFlips (n - 1). Если мы хотим, чтобы перед каждым значением в этом массиве стояло 'H', лучше всего использовать .map. Мы можем id вот так: getFlips (n - 1) .map (r => 'H' + r). И, конечно же, вторая половина просто getFlips (n - 1) .map (r => 'T' + r). Если мы хотим объединить два массива в один, есть много методов, включая .push и .concat. Но современным решением, вероятно, будет использование параметров спреда и просто возврат [...first, ...second].

Собрав все это вместе, мы получаем этот фрагмент:

const getFlips = (n) =>
  n <= 0
    ? ['']
    : [...getFlips (n - 1) .map (r => 'H' + r), ...getFlips (n - 1) .map (r => 'T' + r)]


console .log (getFlips (3))

Изучение результатов

Мы можем проверить это на нескольких случаях. Но мы должны быть достаточно убеждены кодом. Кажется, это работает, это относительно просто, нет очевидных пограничных случаев. Но я все еще вижу проблему. Мы вычисляем getFlips (n - 1) дважды без веской причины. В рекурсивной ситуации это обычно довольно проблематично.

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

Замените условный оператор операторами if-else

const getFlips = (n) => {
  if (n <= 0) {
    return ['']
  } else {
    const prev = getFlips (n - 1)
    return [...prev .map (r => 'H' + r), ...prev .map (r => 'T' + r)]
  }
}

(Технически else не нужен, и некоторые линтеры жаловались бы на него. Я думаю, что код читается лучше, когда он включен.)

Вычислить параметр по умолчанию для использования в качестве локальной переменной

Другим было бы использование значения параметра по умолчанию в более раннем определении.

const getFlips = (n, prev = n > 0 && getFlips (n - 1)) =>
  n <= 0
    ? ['']
    : [...prev .map (r => 'H' + r), ...prev .map (r => 'T' + r)]

Это можно по праву рассматривать как слишком сложное, и это может вызвать проблемы, когда ваша функция используется в неожиданных обстоятельствах. Не передавайте это, например, вызову массива map.

Переосмыслите рекурсивный шаг

Любой из вышеперечисленных будет работать. Но есть лучшее решение.

Мы также можем написать почти такой же код с другим подходом к рекурсивному шагу, если увидим другой способ превращения ['HH', 'HT', 'TH', 'TT'] в ['HHH', 'HHT', 'HTH', 'HTT', 'THH', 'THT', 'TTH', 'TTT']. Наша техника заключалась в том, чтобы разбить массив посередине и удалить первые буквы. Но есть и другие копии этой базовой версии в версии массива без одной из своих букв. Если мы удалим последние буквы из каждого, мы получим ['HH', 'HH', 'HT', 'HT', 'TH', 'TH', 'TT', 'TT'], что является нашей исходной версией, в которой каждая строка встречается дважды.

Первый код, который приходит на ум для реализации этого — просто getFlips (n - 1) .map (r => [r + 'H', r + 'T']). Но это было бы немного неправильно, так как оно преобразовывало бы ['HH', 'HT', 'TH', ' TT'] в [["HHH", "HHT"], ["HTH", "HTT"], ["THH", "THT"], [" TTH", " TTT"]] с дополнительным уровнем вложенности, а рекурсивное применение просто давало бы бессмыслицу. Но есть альтернатива .map, которая удаляет этот дополнительный уровень вложенности, .flatMap.

И это приводит нас к решению, которым я очень доволен:

const getFlips = (n) =>
  n <= 0
    ? ['']
    : getFlips (n - 1) .flatMap (r => [r + 'H', r + 'T'])

console .log (getFlips (3))

person Scott Sauyet    schedule 25.08.2020

arrow_upward
0
arrow_downward

Если это представляет интерес, вот решение, которое не использует рекурсию как таковую, но использует Applicative тип.

За исключением случаев, когда n равно 1, список всех возможных комбинаций получается путем объединения всех возможных результатов каждого подбрасывания монеты:

  • 22 → [H, T] × [H, T] → [HH, HT, TH, TT]
  • 23 → [H, T] × [H, T] × [H, T] → [HHH, HHT, HTH, HTT, THH, THT, TTH, TTT]
  • ...

Функция, которая может принимать n символов и объединять их, может быть записана следующим образом:

const concat = (...n) => n.join('');

concat('H', 'H');           //=> 'HH'
concat('H', 'H', 'T');      //=> 'HHT'
concat('H', 'H', 'T', 'H'); //=> 'HHTH'
//...

Функцию, которая выводит список результатов для n бросков монеты, можно записать следующим образом:

const outcomes = n => Array(n).fill(['H', 'T']);

outcomes(2); //=> [['H', 'T'], ['H', 'T']]
outcomes(3); //=> [['H', 'T'], ['H', 'T'], ['H', 'T']]
// ...

Теперь мы можем увидеть здесь решение: чтобы получить список всех возможных комбинаций, нам нужно применить concat ко всем спискам.

Однако мы не хотим этого делать. Вместо этого мы хотим, чтобы concat работал с контейнерами значений, а не с отдельными значениями.

Так что:

concat(['H', 'T'], ['H', 'T'], ['H', 'T']);

Производит тот же результат, что и:

[ concat('H', 'H', 'H')
, concat('H', 'H', 'T')
, concat('H', 'T', 'H')
, concat('H', 'T', 'T')
, concat('T', 'H', 'H')
, concat('T', 'H', 'T')
, concat('T', 'T', 'H')
, concat('T', 'T', 'T')
]

В функциональном программировании мы говорим, что хотим lift concat. В этом примере я буду использовать функцию Ramda liftN.

const flip = n => {
  const concat = liftN(n, (...x) => x.join(''));
  return concat(...Array(n).fill(['H', 'T']));
};

console.log(flip(1));
console.log(flip(2));
console.log(flip(3));
console.log(flip(4));
<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.27.1/ramda.min.js"></script>
<script>const {liftN} = R;</script>

person customcommander    schedule 25.08.2020
comment
Очень красивый подход! Было бы интересно написать переменную lift, возможно, ограниченную функциями, для использования в подобных ситуациях. - person Scott Sauyet; 25.08.2020
comment
Я не уверен, что мой предыдущий комментарий был последовательным. Но другой подход — это простая функция перекрестного произведения, такая как const crossproduct = (xss) => xss .reduce ((ps, xs) => ps .reduce ((r, p) => [... r, ... (xs .map ((x) => [... p, x]))], []), [[]]), с тем же входом Array(n).fill(['H', 'T']). - person Scott Sauyet; 25.08.2020
comment
Спасибо за ваши комментарии @ScottSauyet, всегда ценю;) Это имеет смысл, хотя я очень предпочитаю вашу рекурсивную плоскую карту. У меня было ощущение, что это можно сделать с ним, но я подумал, что lift тоже может быть альтернативой для рассмотрения. - person customcommander; 25.08.2020
comment
Абсолютно. Я был очарован вашим ответом. Только позже я понял, что то, что вы делаете, уже покрыто функцией crossproduct. - person Scott Sauyet; 25.08.2020