[ML][练习] 生成排列

flw

原帖由 drunkedcat 于 2008-11-17 14:45 发表



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

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

嗯，你说的有道理。

win_hate

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

说白了是按字典序来排。

下面的连接给出了在 Gsl, Maple, Mathematica 中处理排列的例子。其中 Gsl, Mathematica 都提供了 nextperm 接口。

http://blog.chinaunix.net/u/20/showart_87581.html

MMMIX

原帖由 win_hate 于 2008-11-17 13:29 发表
haskell 那个我是这样测的(帮忙看看是否用错了命令)：


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

这个可以直接用 (permutation [1..10000]) !! 10000

我测试了一下，用 -O2 编译后，这个在我的机器(P4 2.2G, 1G 内存)上大概 6.8 左右的样子就可以跑出来。现在用的是 GHC 6.8，改天试试 6.10 的表现。

(permutation [1..10000]) !! 100000 需要的时间大概是 68 秒。

MMMIX 那个空间占得厉害。

是有这个问题。Boxed variable 和 lazy evolution 这两个都会消耗内存。

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

MMMIX

BTW，我把 win_hate 用 ML 实现的 nextperm 翻译为 Haskell 测试了一下，超级快

不过我觉得主要问题在于才用 nextperm 这种方式，程序的执行流程相对简单，好优化；而我原来的实现其执行流程就复杂很多（至少是从实现方面考虑)。

win_hate

把你的 Haskell 代码贴出来给我学习一下吧，我本来想写一个的，刚学的一点语法都忘光了，一点感觉都没有。

ML 加载模块用 load。今天用你那段代码，load List 总是出错，查了一下，原来要用 import,

MMMIX

原帖由 win_hate 于 2008-11-17 20:05 发表
把你的 Haskell 代码贴出来给我学习一下吧，

这是我把你的 ML 代码翻译为 Haskell 后的结果，你可以参考下：

1. 
   
2. module Permutation (nextPerm, nthPerm, allPerm) where
   
3. 
   
4. import Data.List (genericTake, genericIndex, sort)
   
5. 
   
6. nextPerm :: Ord a => [a] -> [a]
   
7. nextPerm (x:xs) = next [x] xs
   
8.   where
   
9.     next rs [] = rs
   
10.     next (r:rs) (y:ys) = if r <= y then next (y:r:rs) ys else swap (r:rs)
    
11.       where
    
12.         swap [x] = y:x:ys
    
13.         swap (x1:x2:xs) = if y < x2 then x1 : swap (x2:xs) else (y:x2:xs) ++ (x1:ys)
    
14. 
    
15. nthPerm :: Ord a => Integer -> [a] -> [a]
    
16. nthPerm n xs = (iterate nextPerm xs) `genericIndex` n
    
17. 
    
18. allPerm :: Ord a => [a] -> [[a]]
    
19. allPerm xs = genericTake (factorial n) $ iterate nextPerm xs'
    
20.   where
    
21.     n = length xs
    
22.     factorial n = product [1..n]
    
23.     xs' = sort xs
    

复制代码

drunkedcat

MMMIX 写得不错，赞一个先。

今天答辩过了，有一点点时间，想一想，把我的取第 n  个组合/排列的程序用 haskell 实现一下，先占个位置。

starfuck

滚

win_hate

原帖由 starfuck 于 2008-11-29 02:58 发表
看起来不怎么样啊，我也秀一个



def factorial(n):
    return reduce(lambda x, y: x*y, xrange(1, n+1), 1)

def nth_permutation(elements, n):
    for i in reversed(xrange(len(elements))):
...

你的代码基于一个事实，n!~0 之间的数可以唯一展开成 a(n-1)(n-1)!+a(n-2)(n-2)!+...+a(1)1!

其中 0<=a(i)<=i

基于这个事实的算法有一个限制，计算阶乘。到目前为止，当 n 比较大时，我们还没有有效计算 n! 的手段。

starfuck

滚