# 工具函数 ↵

我需要一些工具函数更方便的处理字符串

00var replace = (s, idx) => s.slice(0, idx) + s.slice(idx + 1); 
01// replace('123', 0) -> "23"
02// replace('123', 1) -> "13"
03// replace('123', 2) -> "12"
04
05var toArr = str => str.trim().split(' '); 
06// "hello world" -> ["hello", "world"]; 
07// "hello world    " -> ["hello", "world"];

工具函数简单的测试用例

上述的 replace 意图很明显，把某个位点替换成 ''，而 toArr 则是完成对处理结果的格式化（从字符串变成数组）

然后利用 replace 做处理，可以把字符串处理成 x:xs 这种 头 + 尾 的格式。比如 “123” 变成 “2” + “13”, “13” 变成 “1” + “3” 这样。这个特性很有用因为它是一种递归结构，很适合用于递归里面。（尾部里面有头和另一个尾部，然后可以继续拆分下去直到空）

# 递归过程 ↵

递归过程

分析一下求 123 的全排列 123 132 213 232 312 321 的过程。

如图利用 replace 处理 123 的头和尾的所有可能的组合是 123 213 312

然后递归的处理尾 23 13 12 得到 (23, 32) 和 (13, 31) 和 (12, 21)

然后，走一遍这颗树

把 1 应用到 23, 32 得到 123, 132
把 2 应用到 13, 31 得到 213, 231
把 3 应用到 12, 21 得到 312, 321

这样就可以得到 “123” 的全遍历结果 123, 132, 213, 231, 312, 321 共 6 个

因为是递归的处理尾部，因此长度为 n-1 的时候也可以得出期望的结果，此外还需定义递归的基准条件用于收束递归。

# 实现 ↵

以下是我的实现

00// 需要工具函数 replace 
01// 利用工具函数 toArr 可以把结果转化成数组 
02var all = str => {
03    if (str.length === 1) return str + ' '; 
04    
05
06    return str.split('').reduce((acc, cur, idx, its) => {
07        // 子串 
08        var subStr = replace(str, idx); 
09        
10        // 这里相当于 map (+its[idx]) all(subStr).toArray  。。。。 
11        acc += all(subStr).split(' ').map(e => its[idx] + e).join(' ') + ' '; 
12        return acc;
13    }, '');
14}

# 简单的测试用例 ↵

00var a = toArr(all("123")); 
01var b = toArr(all("12")); 
02var c = toArr(all("1")); 
03
04console.log('a: ', a); 
05console.log('b: ', b); 
06console.log('c: ', c);

测试 all 函数

# Links ↵

这其实是我在 SegmentFault 上的一个回答：SF - 一串数字重新组合新数字的算法

学 Haskell 一周了，我已经被她征服了。

逼格函数式编程
简洁易用列表推导式、哨兵、模式匹配
严谨深邃递归的思考、无限列表、惰性求值
符合自然前缀调用、柯里化的函数、函数组合等等