代码之家 › 专栏 › 技术社区 › totalnoob

更好地理解查找字符串排列的解决方案-javascript

javascript

totalnoob · 技术社区 · 7 年前

我试图更好地理解递归和函数编程,我认为一个很好的实践例子是使用递归和现代方法(如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]]

从…起 Permutations in JavaScript? 斯里先生

为了添加一些控制台日志来调试它,并了解它在幕后做什么,我对它进行了一些分隔

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])

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

2 回复 | 直到 7 年前

Jonas Wilms 7 年前

要获得所有置换,我们执行以下操作:

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

 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]

Jorge Adriano Branco Aires 7 年前

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

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

A ,我们将指出 P(A) .

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

基本情况:

[]

P(A) = {[]}

递归情况:

为了使用递归,您需要描述如何获取 P(A) P(A') 对一些人来说 A' A.

注意:如果你这样做,它就完成了。在操作上,该计划将通过连续调用 P 使用越来越小的参数,直到它到达基本情况,然后它将从较短的结果中构建较长的结果。

A. A. 对于每个职位:

 _   _ ... _ 
n+1  n     1

所以你选了一个 x â A

 x   _ ... _ 
     n     1

P(A\{x}) .

n . 考虑所有可能的选择 x 在里面 (用作第一个元素),并为每个选项放置在每个解决方案的前面 P(A\{x}) x .

让我们使用点运算符来表示推杆在序列前面 s ,以及表示推杆的菱形运算符 x 在每个人面前 s â S

xâs = [x, s1, s2, ..., sn] 
xâ¡S = {xâs : s â S}

那么对于一个非空的

P(A) = â {xâ¡P(A\{x}) : x â A}

此表达式与case base一起提供了集合中元素的所有排列 .

要理解您所显示的代码是如何实现这个AlgRoTimthm的,您需要考虑以下内容

当您有0或1个元素时,该代码通过编写 xs.length < 2 . 我们也可以这么做,这无关紧要。你可以把2改成1,它应该还能用。
映射对应于我们的操作 xâ¡S = {xâs : s â S}
无对应于
展平对应于 â