[求助]：随机排列数组的问题！

highflybird

例如有一个数组，元素可能有上百万个，现在要对这个数组的元素随机排列，就像洗牌那样。生成这样一个函数，以供调用。算法上最好能对空间和时间都有照顾！

fsxm

这个难吗？
一新数组记为newlst
{
原数组记为lst ， 数组长为记为n
在0~n-1间生成一随机数记为rnd
用rnd为索引取lst中的一个元素出来放入newlst
在lst中删除取出来的元素
}
重做以上{ }中的步骤直到lst中的元素被全转移到newlst中来
newlst就是所求,
对于你说的:算法上最好能对空间和时间都有照顾
偶知识有限不知道是什么为事呢?请详解

突然想到一新解法了

原表记为lst ， 表长为记为n
随机生成n个数组成表rndlst
对rndlst用vl-sort-i排序后记为sortrndlst
再(mapcar 'nth sortrndlst lst)就是所求了
呵呵相信这个方法的效率非常之好！

highflybird

最初由 fsxm 发布
[B]这个难吗？
一新数组记为newlst
{
原数组记为lst ， 数组长为记为n
在0~n-1间生成一随机数记为rnd
用rnd为索引取lst中的一个元素出来放入newlst
在lst中删除取出来的元素
}
重做以上{ }中的步骤直到lst中的... [/B]

to fsxm：
    谢谢你提供的思路。
    你的第一个方法很好，但是对于第二个方法来说，你可能没有考虑到随机可能生成重复的数目的情况。
    我说的是算法上最好能对空间和时间都有照顾是指：
    1、lisp语言没有求随机数函数，如果要通过VB之类的调用的话，可能速度要慢不少，如果用autolisp编写随机函数，则要考虑不能效率太低。
    2、如果这个数组有一个百万级以上的元素的话，就不得不考虑在调用随机函数时候存储空间的问题了。
    无痕 斑竹在明经发了一个lisp程序，跟你的第一个思路有些类似。可以参阅。
http://www.mjtd.com/BBS/dispbbs. ... mp;star=2&page=

fsxm

我强烈认为第二方法才是最好的！也是最快的！
话不多说传上我写的：
[php]
(defun rndsortlst (lst / rndlst)
  (repeat (length lst)
    (setq rndlst (cons (rnd) rndlst))
  )
  (setq rndlst (vl-sort-i rndlst '>))
  (mapcar '(lambda (a) (nth a lst)) rndlst)
)
调用语法:(rndsortlst lst) 如:(rndsortlst '(0 1  2 3 4 5 6 7 8 9))                ------fsxm2007/01/21
[/php]
rnd生成随机数函数请自己写～
下面我给出一个完整的函数包
里面也加上了rnd生成随机数函数和rndsortlst函数!
可以直接使用！

zml84

最初由 fsxm 发布
[B]对于你说的:算法上最好能对空间和时间都有照顾
偶知识有限不知道是什么为事呢?请详解[/B]

<br>
关于空间与时间复杂度[/COLOR]的解释，参见杨富贵老师在《科幻世界》（2005.05期）卷首特辑中所说：
“计算机科学把完成某个任务（比如搜索）的算法执行所需要的时间量级称为时间复杂度；而把这个算法在运行中数据结构和所需要额外占用的空间的量度，称为空间复杂度。对一个任务，找到空间复杂度和时间复杂度都很小的算法，正是计算机科学家的任务之一。”[/FONT]

这里有全文，可供欣赏：
http://zml84.blog.sohu.com/27261124.html

highflybird

最初由 fsxm 发布
[B]我强烈认为第二方法才是最好的！也是最快的！
话不多说传上我写的：
[php]
(defun rndsortlst (lst / rndlst)
  (repeat (length lst)
    (setq rndlst (cons (rnd) rndlst))
  )
  (setq rndlst (vl-sort-i... [/B]

的确比无痕的快，谢谢fsxm!但还没明白怎么回事，不知能否把那个rnd函数的源码贴上来呢？

雨箭风刀

;; 试试这个

2. 
   
3. (defun C:TT2 (/ ETIME LST N STIME X)
   
4.   (setq        N   0
   
5.         LST NIL
   
6.   )
   
7.   (repeat 10000
   
8.     (setq LST (cons (setq N (1+ N)) LST))
   
9.   )
   
10.   (setq STIME (getvar "date"))
    
11.   ;(setq LST (mapcar '(lambda (X) (nth X LST)) (rndsi (length lst))))
    
12.   (setq lst(rndlst lst))
    
13.   (setq ETIME (getvar "date"))
    
14.   (prompt
    
15.     (strcat
    
16.       "\n程式共耗用時間: "
    
17.       (rtos (* 86400.0 (- (- ETIME STIME) (fix (- ETIME STIME))))
    
18.             2
    
19.             3
    
20.       )
    
21.       "秒\n"
    
22.     )
    
23.   )
    
24.   LST
    
25. )

<br /> (defun C:TT2 (/ ETIME LST N STIME X)<br />   (setq        N   0<br />         LST NIL<br />   )<br />   (repeat 10000<br />     (setq LST (cons (setq N (1+ N)) LST))<br />   )<br />   (setq STIME (getvar "date"))<br />   ;(setq LST (mapcar '(lambda (X) (nth X LST)) (rndsi (length lst))))<br />   (setq lst(rndlst lst))<br />   (setq ETIME (getvar "date"))<br />   (prompt<br />     (strcat<br />       "\n程式共耗用時間: "<br />       (rtos (* 86400.0 (- (- ETIME STIME) (fix (- ETIME STIME))))<br />             2<br />             3<br />       )<br />       "秒\n"<br />     )<br />   )<br />   LST<br /> )