[ML][练习] 生成排列

MMMIX

原帖由 starfuck 于 2008-12-2 00:06 发表
我倒奇怪了，占空间的方式能撑到n!多大还不死的

应该是 n 多大。n 和 n! 的数量级是不能同日而语的。

win_hate

原帖由 starfuck 于 2008-12-2 00:06 发表
我倒奇怪了，占空间的方式能撑到n!多大还不死的

如果在华丽地跳出来之前，能先看一看大家的讨论，就不会提这样的问题了。

MMMIX

原帖由 win_hate 于 2008-12-3 10:43 发表


如果在华丽地跳出来之前，能先看一看大家的讨论，就不会提这样的问题了。

starfuck

滚

win_hate

原帖由 starfuck 于 2008-12-3 19:01 发表
移来移去取1000000个早死了，别说求n!了

我们来比较一下：

你的代码，不带输出的，公平吧？

1. 
   
2. def factorial(n):
   
3.     return reduce(lambda x, y: x*y, xrange(1, n+1), 1)
   
4. 
   
5. def nth_permutation(elements, n):
   
6.     for i in reversed(xrange(len(elements))):
   
7.         x, n = divmod(n, factorial(i))
   
8.         yield elements.pop(x)
   
9. 
   
10. list(nth_permutation(range(1000), 0))
    

复制代码

1. 
   
2. zxl@VIKI:~/src$ time python 1.py
   
3. 
   
4. real    0m1.198s
   
5. user    0m1.064s
   
6. sys     0m0.024s
   

复制代码

注意你这里是1000 个数的排列，取第 0 个。如果是 10000 个数，我这里等了一分钟没出来。

我的代码：

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 10000) x;
    
22. quit();
    

复制代码

一万个数的排列，取第一万零一个，带部分输出的。

1. 
   
2. time mosml 1.sml
   
3. 
   
4. real        0m0.113s
   
5. user        0m0.056s
   
6. sys        0m0.016s
   

复制代码

starfuck

滚

win_hate

原帖由 starfuck 于 2008-12-4 00:27 发表
我写的很清楚，阶乘可以避免重复计算，你看不见吗？


def factorials(n):
    v = 1
    yield v
    for i in xrange(1, n):
        v *= i
        yield v

def nth_permutation(elements, n):
...

如果你真的看得见，就会知道这个比较不公平。而且从一开始就不公平。

关键在于，nextperm 是通过一个排列计算另一个排列，所以在计算第 200000 个排列时，我的已经算出了 200000 个排列。你的只算了一个啊！

要公平比较，你就得用一个循环，计算从 1~200000 的全部排列.

你说的那个内存溢出是解释器造成的, mosml 目前还是个玩具。ML 的标准解释器是 smlnj，我们来看一下

1. 
   
2. def factorials(n):
   
3.     v = 1
   
4.     yield v
   
5.     for i in xrange(1, n):
   
6.         v *= i
   
7.         yield v
   
8. 
   
9. def nth_permutation(elements, n):
   
10.     f = list(factorials(len(elements)))
    
11.     while len(elements):
    
12.         x, n = divmod(n, f.pop())
    
13.         yield elements.pop(x)
    
14. 
    
15. #print list(nth_permutation(range(10000), 10**7878))
    
16. print list(nth_permutation(range(10000), 200000))
    

复制代码

今天只有一个很旧的机器，256M 内存。不好意思。

1. 
   
2. time python 1.py
   
3. 
   
4. real        0m1.297s
   
5. user        0m0.424s
   
6. sys        0m0.260s
   

复制代码

再来看我的：

1. 
   
2. time sml< 1.sml
   
3. 
   
4. real    0m0.878s
   
5. user    0m0.552s
   
6. sys        0m0.128s
   

复制代码

我这个还可以计算大得多的排列，比如 1000000 个数的第 200000 个排列（其实是前 200001 个啦）

1. 
   
2. time sml < 1.sml
   
3. 
   
4. 
   
5. real        0m4.272s
   
6. user        0m2.388s
   
7. sys        0m0.412s
   

复制代码

[ 本帖最后由 win_hate 于 2008-12-4 10:37 编辑 ]

starfuck

滚

win_hate

我只关心算法，而不是语言。没有用 python 代码跟你的对比，是因为我不太懂 python。把 mosml 换成 smlnj 是因为你用的那个版本内存溢出了。

一开始用计算 m 个排列与你计算 1 个排列比较，是因为觉得你那陀代码太弱了。

后来你把代码改了，总不好意思要我继续让你吧。

我这段代码的目的，前面说得很清楚了。我的是 nextperm，你的是 nthperm，根本不是一回事。

我说 nthperm 在元素过多的情况下不好使，你现在又把代码改了! 你还是在计算 n! 吗？

starfuck

滚