[ML][练习] 生成排列

win_hate

来源：《ML 程序设计教程》3.13 求后继排列的问题

此例子使用的算法描述见：[Generate Permutation].


操作大致分三步：

• 搜索，分段
• 搜索，交换
• 逆转
  

以前用 C 实现过，数据结构为数组。逆转可以通过两个指针（一头一尾）进行交换。用 ML 实现时，使用了列表，在第一步时，通过列表的积累操作，已经把改逆转的逆转掉了。

另外，为了便于列表操作。在 ML 实现中，[4,3,2,1] 是 4 排列中最小的，而 [1,2,3,4] 是最大的。即左边看成低位，而右边看成高位。

[ 本帖最后由 win_hate 于 2008-11-15 14:57 编辑 ]

win_hate

1. 
   
2. fun nextperm (x::xs) =
   
3.     let fun next (r::rs, y::ys) =
   
4.             if r<=y then next(y::r::rs, ys)
   
5.             else let fun swap [x] = y::x::ys
   
6.                        | swap (x1::x2::xs) =
   
7.                          if y<x2 then x1::swap (x2::xs)
   
8.                          else (y::x2::xs)@(x1::ys)
   
9.                  in swap (r::rs) end
   
10.             | next (r, []) = r
    
11.     in next ([x], xs) end;
    

复制代码

1. 
   
2. - nextperm [4,3,2,1];
   
3. > val it = [3, 4, 2, 1] : int list
   
4. - nextperm [2,4,1,3];
   
5. > val it = [4, 1, 2, 3] : int list
   
6. - nextperm [1,2,3,4];
   
7. > val it = [4, 3, 2, 1] : int list
   

复制代码

drunkedcat

MMMIX 用 Haskell 写的版本要简单很多，呵呵

flw

原帖由 drunkedcat 于 2008-11-17 08:44 发表
MMMIX 用 Haskell 写的版本要简单很多，呵呵

不要太在意语法糖，那些都是浮云，关键是思想。

MMMIX

原帖由 flw 于 2008-11-17 09:22 发表

不要太在意语法糖，那些都是浮云，关键是思想。

对研究算法来说也许是这样，但对于编程语言本身来说，提供好的(也即易学易用的)语法是非常重要的。

win_hate

MMMIX 的程序在严格求值的语言中，只能对付很小的 n。因为该程序本质上生成全部的，也就是  n! 个排列。

我的那个程序本意不是生成排列全体，而是给定一个排列后，生成其后继排列。

但是，在惰性环境中，MMMIX 的程序可以对付很大的 n，而且性能还不错。这个有点出乎我的意料，看来惰性求值真是个好东西。

不过，从算法上看，生成后继排列的算法仍然占优。我简单测试了一下，用  n=10000，取产生序列中的第 10000 个排列。用顶楼的算法可以马上算出。用生成全部排列那个我没等它算完，内存已经涨得很厉害了。

生成后继排列的算法时间，空间复杂度都是 O(n), MMMIX 那个空间占得厉害。

[ 本帖最后由 win_hate 于 2008-11-17 13:30 编辑 ]

win_hate

haskell 那个我是这样测的(帮忙看看是否用错了命令)：

1. 
   
2. let x = permutation [1..10000]
   
3. take 1 (drop 10000 x)
   

复制代码

用 ML 的代码如下：

1. 
   
2. fun upto 0 = []
   
3.   | upto n = n:: upto (n-1)
   
4. 
   
5. fun nextperm (x::xs) =
   
6.     let fun next (r::rs, y::ys) =
   
7.             if r<=y then next(y::r::rs, ys)
   
8.             else let fun swap [x] = y::x::ys
   
9.                        | swap (x1::x2::xs) =
   
10.                          if y<x2 then x1::swap (x2::xs)
    
11.                          else (y::x2::xs)@(x1::ys)
    
12.                  in swap (r::rs) end
    
13.             | next (r, []) = r
    
14.     in next ([x], xs) end;
    
15. 
    
16. val x = upto 10000;
    
17. 
    
18. fun repeat 1 = nextperm
    
19.   | repeat n = nextperm o repeat (n-1);
    
20. 
    
21. (repeat 100000) x;
    

复制代码

Haskell 那个取第一万个， ML 这个取第十万个。ML 这个也能马上算出。

[ 本帖最后由 win_hate 于 2008-11-17 13:32 编辑 ]

flw

你这个算法太深奥了，
是不是说白了就是 12345 的下一个就是 12346 这样子？
假设有 N 个不重复的元素，那么就是 N 进制 ++ 的问题？

drunkedcat

取第 n 个，这个思想我也很喜欢，曾经用 c 写过一个取第 n 个组合的程序，现在还经常用得到，就是给一组数，直接到到第 n 个组合。

drunkedcat

原帖由 flw 于 2008-11-17 14:12 发表
你这个算法太深奥了，
是不是说白了就是 12345 的下一个就是 12346 这样子？
假设有 N 个不重复的元素，那么就是 N 进制 ++ 的问题？

应该不是 “N 进制的 ++ 问题”，因为元素不可以重复。

比如，只用 12345 五个数字，12345 的下一个应该是 12354 ，而不能是 12351 .