更好地理解查找字符串排列的解决方案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,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,2]，[3]的

有人能一步一步地告诉我引擎盖下面发生了什么吗？

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]

Answer 2

我对它进行了一些分隔，以便添加一些控制台日志来调试它

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

事实上，这也是递归如此有用的原因之一。因为有些算法有复杂的迭代，所以允许简单的递归描述。因此，理解递归算法的目标应该是在其定义中找出归纳(而不是迭代(推理。

让我们忘记javascript，专注于算法。我们可以得到集合A的元素的排列，我们将其表示为P(A)。

注意：在原始算法中，输入是一个列表，这与此无关，因为原始顺序根本不重要。同样，我们将返回一组列表而不是一组列表也没有关系，因为我们不在乎计算解决方案的顺序

基本情况：

最简单的情况是空集。0个元素的排列恰好有一个解，这个解就是空序列[]。所以，

P(A) = {[]}

递归情况：

为了使用递归，您想描述如何从P(A')中获得一些大小小于A的A'的P(A)。

注意：如果你这样做，它就完成了。在操作上，该程序将通过对P的连续调用，使用越来越小的参数进行计算，直到达到基本情况，然后它将从较短的结果中获得更长的结果

因此，这里有一种方法来编写具有n+1个元素的A的特定排列。您需要为每个位置依次选择A的一个元素：

 _   _ ... _ 
n+1  n     1

所以你为第一个选择了一个x ∈ A

 x   _ ... _ 
     n     1

然后你需要在P(A{x})中选择一个置换。

这告诉您一种构建n大小的所有排列的方法。考虑A中x的所有可能选择(用作第一个元素(，并针对每个选择将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})

• 扁平化对应于连接所有解决方案的⋃。