2 июля: Генерация k-комбинаций с рекурсией в JavaScript.

Во-первых, краткий обзор рекурсии из предыдущего моего сообщения в блоге: рекурсия решает большую проблему (рекурсивный случай), многократно решая идентичную, но меньшую проблему ( базовый случай). Базовый вариант выглядит так же, как рекурсивный, только в меньшем масштабе. Рекурсия работает только тогда, когда программа в конечном итоге достигает базового случая; без достижения базового случая, рекурсивный метод будет повторяться бесконечно.

Одно важное различие, которое я не обсуждал, существует между головной рекурсией и хвостовой рекурсией; рекурсивный вызов может происходить до обработки базового случая (вверху или в «голове» функции) или после базового случая (внизу или "хвостик"). Я проиллюстрировал это с помощью двух factorial() функций ниже, которые делают то же самое:

const headFactorial = n => {
  if ( n > 1 ) return n * headFactorial( n - 1 );
  else return 1;
}
const tailFactorial = n => {
  if ( n === 1 ) return 1;
  else return n * tailFactorial( n - 1 );
}

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

Вместе с нашими силами ...

Если набор содержит n элементов, количество k-комбинаций из этого набора может быть выражено как биномиальный коэффициент с факториалами:

Это просто написать, но в нашем примере с покером (52-combo-5) это приводит к некоторым математическим выводам, вызывающим головную боль ...

… Так что давайте разберемся с факторингом:

Это имеет большой смысл, если подумать об этом более конкретно, представив, что вы за покерным столом вытягиваете руку. При вытягивании первой карты у вас есть 52 на выбор, при вытягивании второй у вас есть 51 возможность и так далее. Подумайте об этом: не означает ли это, что каждая комбинация - это просто предыдущие решки, а оставшиеся комбинации прикреплены к хвосту?

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

const combinations = ( collection, combinationLength ) => {
  let head, tail, result = [];
  if ( combinationLength > collection.length || combinationLength < 1 ) { return []; }
  if ( combinationLength === collection.length ) { return [ collection ]; }
  if ( combinationLength === 1 ) { return collection.map( element => [ element ] ); }
  for ( let i = 0; i < collection.length - combinationLength + 1; i++ ) {
    head = collection.slice( i, i + 1 );
    tail = combinations( collection.slice( i + 1 ), combinationLength - 1 );
    for ( let j = 0; j < tail.length; j++ ) { result.push( head.concat( tail[ j ] ) ); }
  }
  return result;
}

Построчное разбиение: сначала мы определяем head и tail, чтобы отслеживать, где мы находимся на данный момент, а затем определяем три базовых случая:

• Затем мы возвращаем пустой массив [], если combinationLength больше, чем размер коллекции, или если combinationLength равно нулю.
• Если combinationLength равно размеру коллекции, возможна только одна комбинация, то есть вся коллекция, поэтому мы возвращаем всю коллекцию в массиве.
• Если combinationLength === 1, наши возможные комбинации - это просто отдельные элементы - поэтому мы возвращаем коллекцию map()ped к ее элементам как отдельные массивы (комбинации) длины 1.

В противном случае мы перебираем коллекцию и начинаем повторяться!

• Наш head будет массивом из одного элемента: того, который находится в текущем индексе, заданном i в цикле for().
• Наш tail будет результатом рекурсивного вызова с combinationLength, уменьшенным на единицу - помните, без уменьшения мы будем повторяться навсегда и выйдет из строя! Мы прикрепляем каждый элемент в tail к концу нашего head, и поскольку каждый представляет новую комбинацию, мы будем push каждый раз result.
• Наконец, конечно, мы return result, когда закончим повторение.

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

const deck = [
  'Two of Clubs',      'Two of Diamonds',   'Two of Hearts',
  'Two of Spades',     'Three of Clubs',    'Three of Diamonds',
  'Three of Hearts',   'Three of Spades',   'Four of Clubs',
  ...trust me they're all there
];
const possibleHands = combinations( deck, 5 );
console.log( possibleHands.length );
  -> 2598960
console.log( possibleHands.slice( 0, 5 ) );
  -> [
    [ 'Two of Clubs', 'Two of Diamonds', 'Two of Hearts', 'Two of Spades', 'Three of Clubs' ],
    [ 'Two of Clubs', 'Two of Diamonds', 'Two of Hearts', 'Two of Spades', 'Three of Diamonds' ],
    [ 'Two of Clubs', 'Two of Diamonds', 'Two of Hearts', 'Two of Spades', 'Three of Hearts' ],
    [ 'Two of Clubs', 'Two of Diamonds', 'Two of Hearts', 'Two of Spades', 'Three of Spades' ],
    [ 'Two of Clubs', 'Two of Diamonds', 'Two of Hearts', 'Two of Spades', 'Four of Clubs' ]
]

Мы видим, что этот метод генерирует правильное количество возможных пятикарточных рук из 52-карточной колоды: 2 598 960, то же самое, что и результат ( 52 * 51 * 50 * 49 * 48 ) / ( 5 * 4 * 3 * 2 ) (проверьте сами, если вы мне не доверяете) .

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

const combinations = ( collection, combinationLength ) => {
  let head, tail, result = [];
  if ( combinationLength > collection.length || combinationLength < 1 ) { return []; }
  if ( combinationLength === collection.length ) { return [ collection ]; }
  if ( combinationLength === 1 ) { return collection.map( element => [ element ] ); }
  for ( let i = 0; i < collection.length - combinationLength + 1; i++ ) {
    head = collection.slice( i, i + 1 );
    console.log( "head: ", head );
    tail = combinations( collection.slice( i + 1 ), combinationLength - 1 );
    console.log( "tail: ", tail );
    for ( let j = 0; j < tail.length; j++ ) { result.push( head.concat( tail[ j ] ) ); }
  }
  return result;
}
const oneThroughFive = [ 1, 2, 3, 4, 5 ];

Если вы скопируете это в консоль узла и запустите, например, combinations( oneThroughFive, 3 ), вы увидите множество журналов, которые выглядят примерно так:

head:  [ 1 ]
head:  [ 2 ]
tail:  [ [ 3 ], [ 4 ], [ 5 ] ]
head:  [ 3 ]
tail:  [ [ 4 ], [ 5 ] ]
head:  [ 4 ]
tail:  [ [ 5 ] ]
tail:  [ [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ]
head:  [ 2 ]
head:  [ 3 ]
tail:  [ [ 4 ], [ 5 ] ]
head:  [ 4 ]
tail:  [ [ 5 ] ]
tail:  [ [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ]
head:  [ 3 ]
tail:  [ [ 4, 5 ] ]
[
  [ 1, 2, 3 ], [ 1, 2, 4 ],
  [ 1, 2, 5 ], [ 1, 3, 4 ],
  [ 1, 3, 5 ], [ 1, 4, 5 ],
  [ 2, 3, 4 ], [ 2, 3, 5 ],
  [ 2, 4, 5 ], [ 3, 4, 5 ]
]

Это очень ясно показывает кое-что интересное: мы никогда не печатаем никаких tail, пока не закончим повторение или не достигнем одного из наших базовых случаев! head всегда представляет собой отдельный элемент из коллекции, с возможными комбинациями из tail, которые наклеиваются, что гарантирует, что комбинации никогда не будут повторяться. На иллюстрации ниже наглядно показано, как все это происходит, когда мы повторяем фрагменты коллекции oneThroughFive с combinationLength равным 3:

Заключение

Никакое умное отслеживание, которое мы используем для генерации k-комбинаций, невозможно с головной рекурсией. Есть и обратные примеры: многие алгоритмы сортировки были бы невозможны с хвостовой рекурсией. И есть еще много примеров рекурсии, лучше всего подходящих для других типов проблем: так называемая круговая или взаимная рекурсия, когда два или более метода рекурсивно вызывают друг друга, наиболее известный студентам CompSci отовсюду от загадки Ханойские башни.

У рекурсии также есть недостатки. Самый большой из них, о котором я упоминал ранее, - это ее потенциал экспоненциального роста, который может замедлить сканирование вашего кода. Если вы копировали этот код в Node, вы заметите, что создание возможных рук из колоды из 52 карт занимает несколько секунд - что не идеально для динамичной игры в покер.

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