把列表里连续的数字合并到连续范围里

论文写得快疯了嗯。上来换口气。

刚才看到问答频道的一个问题，javascript 数组差值排列

bjqincy 写道

一个数组，
[1,2,3,6,9,20,21,34,45,67,68]
将后一个与前一个的差值
假如连续差值等于1，就要将第一元素与最后一个输出
结果
显示为为一个table
显示效果：
1--3
6，
9，
20---21
34
45
67--68

这前提是输入的数组必须是严格升序的，元素不能有重复。不然我下面的代码就都不行了 XD
如果不是严格升序，就得在fold的时候加点判断才行。

要是用F#来做极其简单……只要“叠”一次就好了 XD
用F# 1.9.6.16来做：（注意这个新版F#把List.fold_right改名叫List.foldBack了）

let merge l = List.foldBack (fun e acc ->
  match acc with
  | x :: xs ->
    match x with
    | [a] -> if a - 1 = e then [e; a] :: xs else [e] :: acc
    | [a; b] -> if a - 1 = e then [e; b] :: xs else [e] :: acc
  | _ -> [e] :: acc) l []

printfn "%A" (merge [1; 2; 3; 6; 9; 20; 21; 34; 45; 67; 68])

显示：

[[1; 3]; [6]; [9]; [20; 21]; [34]; [45]; [67; 68]]

（怪哉，如果函数名用mergeToRanges，就得把函数体整个用括号包起来。用短一些的名字如m或merge就没事。这是怎么搞的……？发了封email去问原因，等回复ing）

于是把同样的逻辑写成JavaScript也行。不过F#的版本效率会好些，因为F#的表是链表而JavaScript的数组就是……数组。

function foldRight(func, ary, acc) {
    if (0 == ary.length) return acc
    return func(ary[0], foldRight(func, ary.slice(1), acc))
}

function mergeToRanges(ary) {
    return foldRight(function(e, acc) {
        if (0 == acc.length)
            return [[e]].concat(acc)
        if (1 == acc[0].length && acc[0][0] - 1 == e)
            return [[e, acc[0][0]]].concat(acc.slice(1))
        if (2 == acc[0].length && acc[0][0] - 1 == e)
            return [[e, acc[0][1]]].concat(acc.slice(1))
        else
            return [[e]].concat(acc)
    }, ary, [])
}

print(mergeToRanges([1,2,3,6,9,20,21,34,45,67,68]).join('\n'))

显示：

1,3
6
9
20,21
34
45
67,68

（print()是Rhino的内建函数。要在浏览器里试的话用alert()替代。）

嘛，写成JavaScript之后多少有点怪就是了 XD

其实照一般思路要用JavaScript来写也很简单？
我在F#版里要用List.foldBack而不是List.fold是为了保持生成的列表顺序与原表的顺序一致。链表的特征使F#的表非得从后向前构造不可，所以要foldBack。
但JavaScript的数组就是数组，从前向后或从后向前构造都没问题。其实用fold可能对JavaScript来说更直观些。把fold进一步转换为循环，就变成了下面这样：（函数式的味道就没了 = =）

function mergeToRanges(ary) {
    var acc = null
    var last = null
    for (var i = 0; i < ary.length; i++) {
        var e = ary[i]
        if (!acc) {
            last = [e]
            acc = [last]
        } else if (1 == last.length && last[0] + 1 == e) {
            last = [last[0], e]
            acc[acc.length-1] = last
        } else if (2 == last.length && last[1] + 1 == e) {
            last = [last[0], e]
            acc[acc.length-1] = last
        } else {
            last = [e]
            acc = acc.concat(last)
        }
    }
    return acc
}

mergeToRanges([1,2,3,6,9,20,21,34,45,67,68]).join('\n')

输出跟问题里问的不完全一样，不过要转换很方便，就不写了。

当然这种办法效率还不算很理想，特别是反复调用Array.concat()会创建很多小对象，不合算。要改进？回头再说……没空了 T T

继续潜下去鼓捣我的东西去 TvT

评论

4 楼 oCameLo 2009-06-16  

写论文写疯了，用这种东西换口气？不是应该去看看谜片或打开窗子大吼一声之类的么？FX果然是个好孩子。。

3 楼 RednaxelaFX 2009-06-08  

好吧，那改回传统的for……

2 楼 night_stalker 2009-06-08  

修正，上面是 alert(i) ……

1 楼 night_stalker 2009-06-08  

对了，慎用 for .. in

譬如 JE 的页面打开 firebug 控制台，输入 for(i in []){alert(x)} 会让你很烦躁。