Would someone be so kind as to give me a piece of Lisp code that will
take a list and re-arrange its elements in random order? Or if you
don't have code, give me an idea as to how I could do it?
Thank You,
James
In article <··················@news.insync.net>,
James Sablatura <····@insync.net> wrote:
>Would someone be so kind as to give me a piece of Lisp code that will
>take a list and re-arrange its elements in random order? Or if you
>don't have code, give me an idea as to how I could do it?
(setq list (sort #'(lambda (x y)
(declare (ignore x y))
(zerop (random 2)))
list))
--
Barry Margolin
BBN Corporation, Cambridge, MA
······@bbnplanet.com
(BBN customers, call (800) 632-7638 option 1 for support)
Barry Margolin <······@bbnplanet.com> wrote in article
<··········@pasilla.bbnplanet.com>...
> In article <··················@news.insync.net>,
> James Sablatura <····@insync.net> wrote:
> >Would someone be so kind as to give me a piece of Lisp code that
will
> >take a list and re-arrange its elements in random order? Or if you
> >don't have code, give me an idea as to how I could do it?
>
> (setq list (sort #'(lambda (x y)
> (declare (ignore x y))
> (zerop (random 2)))
> list))
>
Very interesting! But terribly inefficient.
A better idea is probably:
a) calculate a random permutation of the first n numbers
(for this task you find solution in most introductory
books about algorithms)
b) transform the input list in a vector
c) use the permutation from a to access the vector elements
and transform the result back to a list.
In Scheme this gives something like:
;;
;; produce a randomly permuted list of the first n numbers
;; maybe the algorithm from C.L. Robinson CA CACM 317
;;
(define (randperm n)
(let
((v (make-vector n 0)))
(do ((i 0 (+ i 1)))
((= i n))
(vector-set! v i i))
(do ((i 0 (+ i 1))
(r (random n) (random n)))
((= i n) (vector->list v))
(let ((h (vector-ref v i)))
(vector-set! v i (vector-ref v r))
(vector-set! v r h)))))
;;
;; get a random permutation of a list
;;
(define (randpermlist lst)
(let*
((v (list->vector lst))
(n (length lst))
(permindex (randperm n)))
(map (lambda (x) (vector-ref v x)) permindex)))
--
Samuel Kilchenmann
········@swissonline.ch
From: David Lowry
Subject: Re: How can I randomize a list?
Date:
Message-ID: <334A7C8C.116B@dbrc.com>
Barry Margolin wrote:
>
> In article <··················@news.insync.net>,
> James Sablatura <····@insync.net> wrote:
> >Would someone be so kind as to give me a piece of Lisp code that will
> >take a list and re-arrange its elements in random order? Or if you
> >don't have code, give me an idea as to how I could do it?
>
> (setq list (sort #'(lambda (x y)
> (declare (ignore x y))
> (zerop (random 2)))
> list))
> --
> Barry Margolin
> BBN Corporation, Cambridge, MA
> ······@bbnplanet.com
> (BBN customers, call (800) 632-7638 option 1 for support)
That code looks extremely dangerous to me. I suspect it could cause
infinite loops, or not return the whole (randomized) list. Obviously, it
depends on how SORT is implemented, but if the comparison function given
to SORT can not consistently differentiate two items, I suspect the
sorting algorithm will break down.
--
[ David D. Lowry
[ Attorney at Law (or at Play) ···@dbrc.com
[ Dike, Bronstein, Roberts & Cushman LLP www.dbrc.com
[ Boston, MA 02109 617 523-3400
[
[ CLOS > (C++ * 10^2)
In article <·············@dbrc.com>, David Lowry <···@dbrc.com> wrote:
>Barry Margolin wrote:
>> (setq list (sort #'(lambda (x y)
>> (declare (ignore x y))
>> (zerop (random 2)))
>> list))
>
>That code looks extremely dangerous to me. I suspect it could cause
>infinite loops, or not return the whole (randomized) list.
"If the :key and predicate functions always return, then the sorting
operation will always terminate, producing a sequence containing the
same elements as the original sequence... This is guaranteed even if
the predicate does not really consistently represent a total order."
CLTL2 sec 14.5.
--
== Seth Tisue <·······@nwu.edu> http://www.cs.nwu.edu/~tisue/
In article <·············@dbrc.com> David Lowry <···@dbrc.com> writes:
>Barry Margolin wrote:
>>
>> (setq list (sort #'(lambda (x y)
>> (declare (ignore x y))
>> (zerop (random 2)))
>> list))
>> --
>
>That code looks extremely dangerous to me. I suspect it could cause
>infinite loops, or not return the whole (randomized) list. Obviously, it
>depends on how SORT is implemented, but if the comparison function given
>to SORT can not consistently differentiate two items, I suspect the
>sorting algorithm will break down.
>--
>
This code is valid, if less than optimal.
Moreover, CLtL2 p. 408 and CL HyperSpec (e.g.,
http://www/harlequin.com/books/HyperSpec/Body/fun_sortcm_stable-sort.html)
state explicitly that SORT, when given terminating PREDICATE and KEY
functional arguments, must always terminate, and must always retain
all elements of the input sequence.
Nonetheless, this example fails in ACL/Win v. 2.x and 3.0.1. It works
in all other CLs I have access to.
See http://www.apl.jhu.edu/~hall/Lisp-Notes/Dalton-Pitfalls-List.text
for more discussion of valid and invalid uses of SORT as well as other
pitfalls.
Andrew
--
Andrew Philpot What [I wrote] above could be unarguably true
USC ISI or it could be prima facie false
·······@isi.edu or it could be surreal gibberish
In article <················@vulture.eecs.umich.edu>,
Paul Nielsen <·······@vulture.eecs.umich.edu> wrote:
>········@saturn.cs.waikato.ac.nz (Bernhard Pfahringer) writes:
>> (mapcar #'rest (sort (mapcar #'(lambda (x) (cons (random 1.0) x)) list)
>> #'<
>> :key #'first))
>>
>> But still this approach is O(NlogN), whereas the rotatef on a vector
>> algorithm is linear.
>>
>> cheers, Bernhard
>>
>>
>> --
>> Bernhard Pfahringer
>> ···············@cs.waikato.ac.nz http://www.ai.univie.ac.at/~bernhard
>
>The worst case for most sort algorithms is O(N^2). The average and the
>best cases are O(NlogN). Of course there are exceptions like bucket sort
>which can do better at the loss of generality, but I doubt the built in
>sort function uses this.
>
The most natural *general* sorting algorithm for lists is mergesort.
Its *worst* case performance is O(NlogN). It would be interesting to
know if any CL implementation does not use mergesort.
cheers, Bernhard
--
Bernhard Pfahringer
···············@cs.waikato.ac.nz http://www.ai.univie.ac.at/~bernhard
In article <··········@pasilla.bbnplanet.com> Barry Margolin <······@bbnplanet.com> writes:
In article <··················@news.insync.net>,
James Sablatura <····@insync.net> wrote:
>Would someone be so kind as to give me a piece of Lisp code that will
>take a list and re-arrange its elements in random order? Or if you
>don't have code, give me an idea as to how I could do it?
(setq list (sort #'(lambda (x y)
(declare (ignore x y))
(zerop (random 2)))
list))
This is a cute idea, but an incorrect algorithm. If the length of the
original list is greater than 2, then the different possible orderings
of the output list will not be equiprobable. The probabilities of different
reorderings will depend on the exact sort algorithm used by your lisp,
but they will not be equal.
To see this, assume that the sort algorithm on a list of length n
calls the comparison function a maximum of k times. Then any given
sequence of k t's and nils, resulting from the k calls to
(zerop (random 2))), will always result in the same reordering of the
list. So the probability of any given reordering will always be a
multiple of 1/(2^k). But there are n! reorderings, so the desired
probabilities of 1/n! for each ordering cannot be obtained, since 1/n!
is not a multiple of 1/(2^k).
Andy Latto
·····@harlequin.com
In article <··················@news.insync.net> ····@insync.net (James Sablatura) writes:
> From: ····@insync.net (James Sablatura)
>
> Would someone be so kind as to give me a piece of Lisp code that will
> take a list and re-arrange its elements in random order? Or if you
> don't have code, give me an idea as to how I could do it?
You could make use of the permutation code posted in a recent reply to
another thread to come up with the following simple (but not necessarily
very efficient) algorithm.
(defun random-order (list)
(let ((permutations (permute list)))
(nth (random (length permutations)) permutations)))
To improve efficiency:
If you are always choosing from the same list, then you could arrange to
create the permutations once and then choose from that precomputed
list. In fact, if that is what you would be doing, turning the list
into a vector would be a good idea since that way you get constant time
access to the desired result.
By the way, DON'T TRY THIS ON LARGE LISTS. The space for all the
permuations will eat your machine alive. In other words, don't use this
algorithm for shuffling a deck of cards! A card deck has 52! ~= 10^68
permutations, so you would need lots of memory.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
····@insync.net (James Sablatura) writes:
>
> Would someone be so kind as to give me a piece of Lisp code that will
> take a list and re-arrange its elements in random order? Or if you
> don't have code, give me an idea as to how I could do it?
>
> Thank You,
> James
>
Here are a bunch of methods for shuffling a list. I recommend the first
one (shuffle-list), but some implementations lack a setf method for nthcdr.
PN
---------------- Cut here ----------------
;;; -*- Mode: LISP; Syntax: Common-Lisp -*-
;;;; Copyright (c) 1991, 1992, 1993, 1994, 1995, 1996, 1997 by Paul Eric Nielsen.
;;;; The following software was developed by Paul Eric Nielsen for his
;;;; exclusive use. This software, or excerpts thereof, may be freely
;;;; redistributed, in any medium, provided that you conspicuously and
;;;; appropriately publish on each copy an appropriate copyright notice.
;;;; It may not be sold for profit or incorporated in commercial documents
;;;; (e.g., published for sale on CD-ROM, floppy disks, books, magazines,
;;;; or other form) without the prior written permission of the copyright
;;;; holder. This software is provided AS IS without any expressed or
;;;; implied warranty.
(defvar *copyright*
"Copyright (c) 1991, 1992, 1993, 1994, 1995, 1996, 1997 by Paul Eric Nielsen.
The following software was developed by Paul Eric Nielsen for his
exclusive use. This software, or excerpts thereof, may be freely
redistributed, in any medium, provided that you conspicuously and
appropriately publish on each copy an appropriate copyright notice.
It may not be sold for profit or incorporated in commercial documents
(e.g., published for sale on CD-ROM, floppy disks, books, magazines,
or other form) without the prior written permission of the copyright
holder. This software is provided AS IS without any expressed or
implied warranty.")
;;;------------------------------------------------------------------------
;;;
;;; List shuffle
;;;
;;;------------------------------------------------------------------------
(defun shuffle-list (list)
"General algorithm is to insert each new element at a random
location of the current list."
;; Non-destructive
;; Won't work if there's no setf method for nthcdr
(let ((result nil))
(dolist (l list result)
(push l (nthcdr (random (1+ (length result))) result)))))
(defun shuffle-list1 (list)
(let ((new-list (copy-list list))) ; Skip the copying if destructive
(do ((lst new-list (cdr lst)))
((null lst) new-list)
(rotatef (car lst) (nth (random (length lst)) lst)))))
(defun shuffle-list2 (list)
(let ((new-list (copy-list list))) ; Skip the copying if destructive
(loop for lst on new-list
for i from (length new-list) downto 1
do (rotatef (car lst) (nth (random i) lst)))
new-list))
(defun shuffle-vector (vector)
;; Destructive
(loop for i from (length vector) downto 1
do (rotatef (aref vector (- i 1)) (aref vector (random i))))
vector)
;;; Code to verify that the above shuffling functions produce a fair
;;; shuffle.
;;; (progn
;;; (dotimes (i 100000)
;;; (VERIFY-SHUFFLE (shuffle-list1 '(a b c d e))))
;;; (display-shuffle-result))
;;; Then see if the displayed results and reasonably uniform
(let ((shuffle-count nil))
(defun display-shuffle-result ()
(loop for sct in shuffle-count
do (format t "~%~A" sct)))
(defun verify-shuffle (list)
(do ((l list (cdr l))
(sct shuffle-count (cdr sct))
(entry nil))
((or (null l) (null sct))
(when (and l (null sct))
(setf shuffle-count
(nconc shuffle-count
(loop for ll in l
collect (list (cons ll 1)))))))
(if (setf entry (find (car l) (car sct) :key #'car))
(incf (cdr entry))
(push (cons (car l) 1) (car sct))))))
;;; Simple sort function (by way of example)
(defun qsort (list &key (function #'>))
;; If LIST is simple, then return it, otherwise do
;; a partition around first element and sort the parts.
(let ((split1 nil)
(split2 nil))
(cond ((null (cdr list)) list)
(T (dolist (l (cdr list))
(if (funcall function l (car list))
(push l split1)
(push l split2)))
(nconc (qsort split1)
(cons (car list)
(qsort split2)))))))
(defun SHUFFLE (list)
"Returns a random permutation of the list
Example:
(shuffle '(1 2 3 4 5 6 7 8 9 10))
;=> (2 8 5 1 7 3 10 6 4 9)
"
;; This algorithm may be thought of as stacking cards pulled randomly from
;;a deck. As such it is easy to see it is unbiased. The pull deck
;;is the beginning of the array, and the stack is the end of the
;;array.
(let ((vector (coerce list 'simple-vector)))
(loop for i fixnum from (length vector) downto 2
do (rotatef (svref vector (1- i)) (svref vector (random i))))
(coerce vector 'list)
))
(defun CUT-DECK (list)
"Cut the deck (list) into two parts using a normal distribution
centered on the middle of the deck.
Returns two values: the two packs.
Example:
(cut-deck '(1 2 3 4 5 6 7 8 9 10))
;=> (1 2 3 4) (5 6 7 8 9 10)
"
(let* ((len (length list))
(split (loop for i below 5
for split = (random len) then (+ split (random len))
finally (return (round split 5))))
(pack1 list)
(pack2 (nthcdr split list))
(mark (nthcdr (1- split) list)))
(setf (cdr mark) nil)
(values pack1 pack2)))
(defun RIFFLE-SHUFFLE (list)
"Simulate a riffle shuffle on a list.
Example:
(riffle-shuffle '(1 2 3 4 5 6 7 8 9 10))
;=> (1 5 6 7 2 3 4 8 9 10)
"
(multiple-value-bind (deck1 deck2)
(cut-deck list)
(let ((result nil)
(swap (= (random 2) 0)))
(flet ((riffle (deck)
;; Drop cards with a 100% chance of 1, 50% chance
;;of 2, 25% chance of 3, and so forth
(do ((r (random 1.0))
(p 1.0 (/ p 2)))
((or (< p r) (null deck)) deck)
(push (pop deck) result))))
(do ((d1 (if swap deck1 deck2) (riffle d1))
(d2 (if swap deck2 deck1) (riffle d2)))
((and (null d1) (null d2))))
)
(nreverse result)
)))
(defun OVERHAND-SHUFFLE (list)
"Simulate an overhand shuffle on a list
Example:
(overhand-shuffle '(1 2 3 4 5 6 7 8 9 10))
;=> (7 8 9 10 6 3 4 5 1 2)
"
(do ((result nil))
((null list) result)
;; Drop cards with a 100% chance of 1, 50% chance of 2, 25% chance
;; of 3, and so forth
(do ((r (random 1.0))
(p 1.0 (/ p 2))
(stack nil (cons (pop list) stack)))
((or (< p r) (null list))
(setf result (nconc (nreverse stack) result))))
))
(defun test-shuffle (times)
(dotimes (i times)
(format t "~%~%~%")
(let ((deck (loop for i from 1 to 52 collect i)))
(dotimes (j 8)
(setf deck (riffle-shuffle deck)))
(dolist (d deck)
(format t "~D " d)))))
Paul Nielsen <·······@vulture.eecs.umich.edu> writes:
>
> ····@insync.net (James Sablatura) writes:
> >
> > Would someone be so kind as to give me a piece of Lisp code that will
> > take a list and re-arrange its elements in random order? Or if you
> > don't have code, give me an idea as to how I could do it?
> >
> > Thank You,
> > James
> >
>
> Here are a bunch of methods for shuffling a list. I recommend the first
> one (shuffle-list), but some implementations lack a setf method for nthcdr.
>
> PN
Scratch that recommendation. Further down in the file there's a function
"SHUFFLE" which is about two orders of magnitude faster than any of the
"suffle-list" functions. (Sorry about that.)
Someone else recommended that you pick a random permutation from the code I
posted earlier, DON'T DO IT. The permutation code will die when trying to
permute about 10 elements. SHUFFLE can randomize a list of 10,000
elements in about 70 ms and only uses as many cons cells as the size of the
list. (If you're really pressed for space, shuffle-list1 and shuffle-list2
can be made destructive by removing the call to "copy-list".)
PN