Комбинаторика — подсчет комбинаций игральных костей с использованием JavaScript

Довольно часто мне задавали вопросы типа:

«Как я могу получить все возможные комбинации для данного броска костей?»

«Сколько комбинаций в сумме дает 7 в паре костей?»

«Можно ли использовать рекурсивный алгоритм для подсчета всех комбинаций игральных костей?»

Чтобы ответить на эти вопросы (и их варианты, связанные с монетами, колодами карт и так далее), мы можем использовать комбинаторика раздел математики, изучающий комбинации объектов, принадлежащих конечному набору элементов.

Хотя я не эксперт в этом вопросе, в этом посте я постараюсь показать вам, как решить комбинаторика используя JavaScript.

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

Перестановки все возможные комбинации данного списка упорядоченных значений. Например, при вычислении всех возможных перестановок для двух шестигранных игральных костей пары {1, 6} и {6,1} считаются разными. Порядок имеет значение.

При подсчете комбинации , пары {1, 6} и {6, 1} считаются одинаковыми. Итак, как это бывает, когда мы работаем с множествами, порядок не имеет значения.

Чтобы поразить двух зайцев одним выстрелом, мы не будем использовать петли. С точки зрения производительности использование рекурсивных функций вместо циклов нет самый эффективный способ (по крайней мере, не в JavaScript), но, поскольку большинство людей просили рекурсивное решение, это путь, который мы собираемся выбрать.

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

const SIDES = 6;
function append(src, num) {
  res = Array.from(src);
  res.push(num);
  return res;
}

function diceCombinations(dc, acc, side, res) {
  if (dc < 1 || side >= (SIDES + 1))
    return;

if (dc == 1) {
    let set = append(acc, side);
    res.push(set);
  }
  else {
    diceCombinations(dc — 1, append(acc, side), side, res);
  }
  return diceCombinations(dc, acc, side + 1, res);
}

За 2 кости предыдущая функция возвращает 21 уникальная комбинация.

Конечно.

Нет, подождите!

6 граней на кубике * 2 кубика = 6**2 = 36 возможных комбинаций!

Вообще говоря, ваша математика верна; Но имейте в виду, что мы считаем уникальные наборы значений; В этой настройке , пары {1, 2} и {2, 1} считаются одинаковыми. И поэтому правильный ответ 21.

Если мы используем 3 кости, это будет 56, и так далее…

(Если вас интересует теория/математика комбинаторики, я рекомендую вам взглянуть на это короткая статья. Не беспокойтесь, вам не нужна докторская степень. понять это )

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

function diceCombinations(dc, acc, side, target, res) {
  if (dc < 1 || side >= (SIDES + 1))
    return;
   if (dc == 1) {
     let set = append(acc, side);
     if (sumSet(set, 0) == target)
       res.push(set);
     }
     else {
       diceCombinations(
         dc — 1, append(acc, side), side, target, res);
  }
  return diceCombinations(dc, acc, side + 1, target, res);
}

Я также добавил вспомогательную функцию для суммирования элементов набора. (Просто ради интереса я тоже сделал его рекурсивным.)

// Sums the value of all members in the set.
function sumSet(set, idx) {
  if (idx >= set.length)
    return 0;
  return set[idx] + sumSet(set, idx + 1);
}

Теперь наша функция позволяет нам ответить:

«Сколько комбинаций в сумме дает 7 при броске пары костей?»

{1, 6} {2, 5} {3, 4}

«Что, если мы используем 3?»

{1, 1, 5} {1, 2, 4} {1, 3, 3} {2, 2, 3}

Итак, вот и все для этого короткого поста. Я надеюсь, что это поможет вам немного узнать о комбинаторике.

Спасибо за чтение!

Увидимся в следующий раз.

Прежде чем ты уйдешь. Если вы только начинаете работать с алгоритмами и структурами данных, вам может быть интересна моя электронная книга « Структуры данных с нуля — версия JS (Это бесплатно для участников Kindle Unlimited.)

Структуры данных с нуля — JS Edition