Hi all,
I'm currently using something like the following code to generate a
permutation of *N* integers (1 through *N* inclusive) in an *N*-length array:
(defconstant *N* 100)
(defvar *PERM* (make-array *N* :initial-element 0)
"Array to hold permutation")
(defvar *CHECK* (make-array *N* :initial-element 0)
"Flags to check if a number has already been generated")
(defun permute ()
(dotimes (i *N*)
(let ((j (do ((r (1+ (random *N*)) (1+ (random *N*))))
((zerop (aref *CHECK* (1- r))) r))))
(setf (aref *CHECK* (1- j)) 1)
(setf (aref *PERM* i) j))))
The do loop that eventually returns a value to bind to "j" keeps generating
random numbers until it finds one that hasn't been generated yet. The
appropriate "flag" is then set in the *CHECK* array and the number is added to
the permutation (the array *PERM*). The whole do loop construct strikes me as
overkill, so I'm curious if anyone has a more effecient approach? Thanks for
any suggestions.
Kris A. Schneider
---------------------------------------------------------------------
Net Xerox 800 Phillips Rd.
············@xerox.com Kris:Wbst129:Xerox Xerox Corp.
716.422.5013 8*222-5013 (x25013) Mail Stop: 129-39A
Webster, NY 14580
---------------------------------------------------------------------
I would be inclined to do something like the following. ALL-PERMUTATIONS will
compute all permutations (here represented as lists), while RANDOM-PERMUTATION
will return a single random permutation.
(defun all-permutations (n)
"Returns a list of all permutations of the integers 1 .. N. Each
permutation is represented as a list. N must be an integer greater than 0."
(if (= n 1)
(list (list 1))
(let ((other-permutes
(all-permutations (1- n))))
;; for each permutation of 1 .. n-1, stick n in at all possible
;; places
(mapcan
#'(lambda (seq)
(let ((res-list nil))
(dotimes (i n res-list)
(push
(nconc (subseq seq 0 i)
(cons n
(subseq seq i)))
res-list))))
other-permutes))))
(defun random-permutation (n)
"Returns a list of the integers 1 .. N in some random permutation.
N must be an integer greater than 0."
(if (= n 1)
(list 1)
(let ((other-permute
(random-permutation (1- n)))
(i (random n)))
;; stick N in just before the I'th elt of OTHER-PERMUTE
(if (zerop i)
(cons n other-permute)
(let ((spot (nthcdr (1- i) other-permute)))
(setf (cdr spot) (cons n (cdr spot)))
other-permute)))))
Dan