лучше понять решение для поиска перестановок строки - JavaScript

Question

Я пытаюсь лучше понять рекурсию, а также функциональное программирование. Я подумал, что хорошим примером для этого будет создание перестановок строки с помощью рекурсии и современных методов, таких как Reduce, Filter и Map.

Я нашел этот прекрасный кусок кода

const flatten = xs =>
    xs.reduce((cum, next) => [...cum, ...next], []);

const without = (xs, x) =>
    xs.filter(y => y !== x);

const permutations = xs =>
    flatten(xs.map(x =>
        xs.length < 2
            ? [xs]
            : permutations(without(xs, x)).map(perm => [x, ...perm])
    ));
    
permutations([1,2,3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

из Перестановки в JavaScript? от Márton Sári

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

const flatten = xs => {
  console.log(`input for flatten(${xs})`);
  return xs.reduce((cum, next) => {
    let res = [...cum, ...next];
    console.log(`output from flatten(): ${res}`);
    return res;
  }, []);
}

const without = (xs, x) => {
  console.log(`input for without(${xs},${x})`)
  let res = xs.filter(y => y !== x);
  console.log(`output from without: ${res}`);
  return res;
}

const permutations = xs => {
  console.log(`input for permutations(${xs})`);
  let res = flatten(xs.map(x => {
    if (xs.length < 2) {
      return [xs]
    } else {
      return permutations(without(xs, x)).map(perm => [x, ...perm])
    }
  }));
  console.log(`output for permutations: ${res}`)
  return res;
}

permutations([1,2,3])

Я думаю, что у меня есть достаточно хорошее представление о том, что делает каждый метод, но я просто не могу представить, как все это объединяется для создания [[1,2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

может кто-нибудь шаг за шагом показать мне, что происходит под капотом?

Answer 1

Я немного ограничил его, чтобы добавить журналы консоли для его отладки

Это может помочь, конечно.Однако имейте в виду, что простые рекурсивные определения часто могут привести к сложным трассам выполнения.

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

Давайте забудем о JavaScript и сосредоточимся на алгоритме.Давайте посмотрим, сможем ли мы получить перестановки элементов множества A, которые мы будем обозначать P(A).

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

Базовый случай:

Простейшим случаем является пустой набор.Существует ровно одно решение для перестановок 0 элементов, и это решение является пустой последовательностью [].Итак,

P(A) = {[]}

Рекурсивный случай:

Чтобы использовать рекурсию, вы хотите описать, как получить P(A) из P(A') для некоторых A' меньше чем A по размеру.

Примечание. Если вы это сделаете, все будет готово.Оперативно программа будет работать через последовательные вызовы P с меньшими и меньшими аргументами, пока не достигнет базового случая, а затем вернется к более длинным результатам из более коротких.

Так вотодин способ написать конкретную перестановку A с n + 1 элементом.Вам нужно последовательно выбрать один элемент из A для каждой позиции:

 _   _ ... _ 
n+1  n     1

Таким образом, вы выбираете x ∈ A для первого

 x   _ ... _ 
     n     1

И затем вам нужно выбратьперестановка в P(A\{x}).

Это говорит вам об одном способе построения всех перестановок размером n.Рассмотрите все возможные варианты x в A (для использования в качестве первого элемента), и для каждого варианта поставьте x перед каждым решением P(A\{x}).Наконец, возьмите объединение всех решений, которые вы нашли для каждого выбора x.

. Давайте использовать оператор точки, чтобы представить размещение x перед последовательностью s, и оператор ромба, чтобы представить размещениеx перед каждым s ∈ S.То есть

x⋅s = [x, s1, s2, ..., sn] 
x⟡S = {x⋅s : s ∈ S}

Тогда для непустого A

P(A) = ⋃ {x⟡P(A\{x}) : x ∈ A} 

Это выражение вместе с основанием падежа дает вам все перестановки элементов в наборе A.

код javascript

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

• Этот код учитывает два базовых случая, когда у вас есть 0 или 1 элемент, путем записи xs.length < 2.Мы могли бы сделать это тоже, это не имеет значения.Вы можете изменить это 2 на 1, и оно все равно должно работать.

• Отображение соответствует нашей операции x⟡S = {x⋅s : s ∈ S}

• Без соответствуетдо P(A\{x})

• Сглаживание соответствует ⋃, который объединяет все решения.

Answer 2

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

Мы берем один элемент массива слева направо.

 xs.map(x => // 1

Для всех остальных элементов мы рекурсивно генерируем перестановки:

 permutations(without(xs, x)) // [[2, 3], [3, 2]]

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

 .map(perm => [xs, ...perm]) // [[1, 2, 3], [1, 3, 2]]

Теперь это повторяется для всех элементов массива, что приводит к:

 [
  // 1
  [[1, 2, 3], [1, 3, 2]],
  // 2
  [[2, 1, 3], [2, 3, 1]],
  // 3
  [[3, 1, 2], [3, 2, 1]]
]

Теперь нам просто нужно flatten(...) этот массив, чтобы получить желаемый результат.

Все это можно выразить в виде дерева рекурсивных вызовов:

 [1, 2, 3]
        - [2, 3] -> 
                   - [3] -> [1, 2, 3]
                   - [2] -> [1, 3, 2]
        - [1, 3] ->
                  - [1] -> [2, 3, 1]
                  - [3] -> [2, 1, 3]
        - [1, 2] -> 
                 - [1] -> [3, 2, 1]
                 - [2] -> [3, 1, 2]