更好地理解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]]。

请问有人可以逐步展示发生了什么吗？

- totalnoob

---

排列方式是逐步递归地创建的，首先检查是否只有一个元素存在，因为此时除了它本身没有其他排列方式。然后递归地应用简单的步骤，尝试每个项目并与其余部分进行排列。 - Nikos M.

Answer 1

为了得到所有排列，我们按照以下步骤进行：

我们从左到右取出数组中的一个元素。

 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]

- Jonas Wilms

---

递归魔法在permutations()函数内部生成排列，它是如何从without()获取其他元素的呢？ - totalnoob

Answer 2

我稍微改了一下，以便添加一些控制台日志来调试它。

这当然有所帮助。但请记住，简单的递归定义通常会导致复杂的执行轨迹。

事实上，这就是递归可以如此有用的原因之一。因为一些具有复杂迭代过程的算法可以简单地进行递归描述。因此，你在理解递归算法时的目标应该是找出其定义中的归纳（而不是迭代）推理。

让我们忘记 JavaScript，专注于算法。让我们看看如何获得集合 A 的元素的排列，我们将它表示为 P(A)。

注意：原始算法中输入是一个列表并不重要，因为原始顺序根本不重要。同样重要的是，我们将返回一个列表的集合而不是一个列表的列表，因为我们不关心计算解决方案的顺序。

基本情况：

最简单的情况是空集。对于 0 个元素的排列，只有一个解决方案，即空序列 []。因此，

P(A) = {[]}

递归情况：

为了使用递归，您需要描述如何从大小小于A的某个A'中获取P(A')以获得P(A)。

注意：如果这样做，就完成了。操作上，程序将通过对带有越来越小的参数的连续调用来计算，直到它达到基本情况，然后它将返回从较短结果构建更长结果。

因此，以下是编写n + 1个元素的A的特定排列的一种方法。您需要依次选择A的每个位置的一个元素：

 _   _ ... _ 
n+1  n     1

所以你首先选择一个 x ∈ A。

 x   _ ... _ 
     n     1

然后您需要在P(A\{x})中选择一个排列。

这告诉您构建所有大小为n的排列的一种方法。考虑在A中选择所有可能的x（用作第一个元素），并且对于每个选择，在P(A\{x})的每个解决方案之前放置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}) - 展平对应于连接所有解的⋃。

- Jorge Adriano Branco Aires