更好地理解查找字符串排列的解决方案 - javascript [英] understanding better a solution for finding permutations of a string - javascript
问题描述
我正在努力更好地理解递归和函数式编程,我认为这是一个很好的实践示例,即使用递归和现代方法(如reduce,filter和map)创建字符串的排列。
I'm trying to get a better understanding of recursion as well as functional programming, I thought a good practice example for that would be to create permutations of a string with recursion and modern methods like reduce, filter and 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]]
来自< a href =https://stackoverflow.com/questions/9960908/permutations-in-javascript> JavaScript中的排列?MártonSári的
from Permutations in JavaScript? by Márton Sári
为了添加一些控制台日志来调试它并理解它在幕后做了什么,我将它分隔了一段时间
I've delimited it a bit in order to add some console logs to debug it and understand what's it doing behind the scenes
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]]
I think I have a good enough idea of what each method iss doing, but I just can't seem to conceptualize how it all comes together to create [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
有人可以一步一步地告诉我幕后发生了什么吗?
can somebody show me step by step what's going on under the hood?
推荐答案
为了获得所有的修改,我们执行以下操作:
To get all permuations we do the following:
我们从左到右获取数组的一个元素。
We take one element of the array from left to right.
xs.map(x => // 1
对于所有其他元素,我们以递归方式生成排列:
For all the other elements we generate permutations recursively:
permutations(without(xs, x)) // [[2, 3], [3, 2]]
对于每个排列,我们添加我们在开头时取回的值:
for every permutation we add the value we've taken out back at the beginning:
.map(perm => [xs, ...perm]) // [[1, 2, 3], [1, 3, 2]]
现在对所有数组元素重复,结果是:
now that is repeated for all the arrays elements and it results in:
[
// 1
[[1, 2, 3], [1, 3, 2]],
// 2
[[2, 1, 3], [2, 3, 1]],
// 3
[[3, 1, 2], [3, 2, 1]]
]
现在我们只需 flatten(...)
该数组即可获得所需的结果。
now we just have to flatten(...)
that array to get the desired result.
整个事情可以表示为递归调用树:
The whole thing could be expressed as a tree of recursive calls:
[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]
这篇关于更好地理解查找字符串排列的解决方案 - javascript的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!