程序员经验分享-hwhale

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

2023-11-30

我试图更好地理解递归和函数式编程，我认为一个很好的实践示例是使用递归和现代方法（如简化、过滤和映射）创建字符串的排列。

我发现了这段漂亮的代码

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

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

我认为我对每种方法的作用有足够的了解，但我似乎无法概念化它们如何组合在一起来创建 [[1, 2, 3], [1, 3, 2], [2 , 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 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]
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

javascript

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

随机推荐

热门标签