Prev: ANUSHKA HOT PICTURES
Next: TextMate Common Lisp Bundle
From: w_a_x_man on 1 Aug 2010 21:18
On Aug 1, 10:22 am, Haris Bogdanoviæ <fbogdano...(a)xnet.hr> wrote:
> Hi.
>
> How to randomize a list ?
>
> Thanks

(1..9).sort_by{ rand }
[7, 1, 3, 5, 9, 2, 6, 8, 4]
From: Gene on 1 Aug 2010 22:19
On Aug 1, 11:22 am, Haris Bogdanoviæ <fbogdano...(a)xnet.hr> wrote:
> Hi.
>
> How to randomize a list ?
>
> Thanks

This algorithm permutes a list in place by changing cdr's. It
provably generates all permutations with equal probability, is
probabilistically faster than quicksort on randomly ordered input, and
uses O(log n) space. Note that traversing the resulting list is a
cache designer's worst nightmare.

(defun randomize (x)
(labels ((f (p len tail)
(cond ((null p) tail)
(t (loop
with ne = (random len)
with e = nil
with n1 = 0
with n2 = 0
with l1 = nil
with l2 = nil
with next = nil
repeat len
do
(setf next (cdr p))
(cond ((zerop ne) (setf e p))
(t
(cond ((zerop (random 2))
(setf (cdr p) l1)
(setf l1 p)
(incf n1))
(t
(setf (cdr p) l2)
(setf l2 p)
(incf n2)))))
(decf ne)
(setf p next)
finally
(setf (cdr e) tail)
(return (if (> n1 n2)
(f l1 n1 (f l2 n2 e))
(f l2 n2 (f l1 n1 e)))))))))
(f x (length x) nil)))

(defun test ()
(loop with count-table = (make-hash-table :test #'equal)
repeat 1000000
for perm = (randomize (list 'a 'b 'c 'd))
do (incf (gethash perm count-table 0))
finally (loop
for perm being each hash-key in count-table
using (hash-value count)
do (format t "~a: ~a~%" perm count))))
From: w_a_x_man on 2 Aug 2010 01:02
On Aug 1, 9:19 pm, Gene <gene.ress...(a)gmail.com> wrote:
> On Aug 1, 11:22 am, Haris Bogdanoviæ <fbogdano...(a)xnet.hr> wrote:
>
> > Hi.
>
> > How to randomize a list ?
>
> > Thanks
>
> This algorithm permutes a list in place by changing cdr's.  It
> provably generates all permutations with equal probability, is
> probabilistically faster than quicksort on randomly ordered input, and
> uses O(log n) space.  Note that traversing the resulting list is a
> cache designer's worst nightmare.
>
> (defun randomize (x)
>   (labels ((f (p len tail)
>              (cond ((null p) tail)
>                    (t (loop
>                          with ne = (random len)
>                          with e = nil
>                          with n1 = 0
>                          with n2 = 0
>                          with l1 = nil
>                          with l2 = nil
>                          with next = nil
>                          repeat len
>                          do
>                            (setf next (cdr p))
>                            (cond ((zerop ne) (setf e p))
>                                  (t
>                                   (cond ((zerop (random 2))
>                                          (setf (cdr p) l1)
>                                          (setf l1 p)
>                                          (incf n1))
>                                         (t
>                                          (setf (cdr p) l2)
>                                          (setf l2 p)
>                                          (incf n2)))))
>                            (decf ne)
>                            (setf p next)
>                          finally
>                            (setf (cdr e) tail)
>                            (return (if (> n1 n2)
>                                        (f l1 n1 (f l2 n2 e))
>                                        (f l2 n2 (f l1 n1 e)))))))))
>     (f x (length x) nil)))
>
> (defun test ()
>   (loop with count-table = (make-hash-table :test #'equal)
>        repeat 1000000
>        for perm = (randomize (list 'a 'b 'c 'd))
>        do (incf (gethash perm count-table 0))
>        finally (loop
>                   for perm being each hash-key in count-table
>                            using (hash-value count)
>                   do (format t "~a: ~a~%" perm count))))

Thanks for helping me.
From: Marc Mientki on 2 Aug 2010 02:25
Am 01.08.2010 18:25, schrieb Haris Bogdanović:
>
> I mean like having a list of numbers from 1 to 10
> and then randomize their order in list.

I wrote in emacs lisp for this purposes random-list
(sorry for german doc string):

(defun random-list (len &optional unique min max)
"Erzeugt eine Liste mit Zufalszahlen im Bereich von MIN bis
MAX. Wenn UNIQUE nicht nil ist, dürfen sich keine Elemente in der
Liste wiederholen. Falls LEN größer ist als die Differenz
zwischen MIN und MAX und UNIQUE dabei nicht nil, dann kann die
Liste nicht erzugt werden und als Ergebnis wird nil
zurückgelifert."
(if (not min)
(setq min 1))
(if (not max)
(setq max len))
(if (or (and unique (<= len (+ (- max min) 1))) (not unique))
(let ((i 0)
elt
(res nil))
(random t)
(while (< i len)
(setq elt (+ (random (+ (- max min) 1)) min))
(when (or (not unique) (not (member elt res)))
(setq res (cons elt res))
(setq i (1+ i))))
res)
nil))


Examples:

(random-list 10)
(6 10 2 2 10 7 7 1 9 4)

(random-list 10 t)
(10 1 7 9 2 6 8 3 5 4)

(random-list 10 nil 0 20)
(6 6 2 16 13 2 17 8 16 14)

(random-list 10 t 0 20)
(12 14 10 20 19 15 1 18 11 4)


HTH
regards
Marc
From: w_a_x_man on 2 Aug 2010 10:58
On Aug 1, 8:18 pm, w_a_x_man <w_a_x_...(a)yahoo.com> wrote:
> On Aug 1, 10:22 am, Haris Bogdanoviæ <fbogdano...(a)xnet.hr> wrote:
>
> > Hi.
>
> > How to randomize a list ?
>
> > Thanks
>
> (1..9).sort_by{ rand }
> [7, 1, 3, 5, 9, 2, 6, 8, 4]

Bigloo Scheme:

1:=> (map (lambda (p) (cadr p))
(sort (lambda (a b) (< (car a)(car b)))
(map (lambda(n)(list (random 99888777) n))
(iota 10 1))))
(6 8 2 4 7 10 9 1 5 3)
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: ANUSHKA HOT PICTURES
Next: TextMate Common Lisp Bundle