Re: Go Fish game in Lisp

From: rif (rif_at_mit.edu)
Date: 12/04/04 

Date: 04 Dec 2004 14:14:01 -0500

Marcin 'Qrczak' Kowalczyk <qrczak@knm.org.pl> writes:

> Jim Newton <jimka@rdrop.com> writes:
>
> > I have a function for shuffling a list into random order.
> > I'm not sure if it is really sound though.
> >
> > (defun rnd-t-nil (a b)
> > (declare (ignore a b))
> > (zerop (random 2)))
> >
> > (defun shuffle-list (elements)
> > (sort elements #'rnd-t-nil))
>
> It doesn't guarantee equal probabilities of all permutations.
>
> For example if sort uses insertion sort, elements would have a high
> chance of being left close to their original positions. With other
> algorithms it needs not to be fair too.

I use this code for taking random permutations and subsets. It will
be more efficient to work with vectors rather than lists for this
purpose.

The basic mathematical idea is that we can randomly permute a vector
of length n by swapping the first element of the vector with a random
(possibly also the first) element. After this swap, the first element
in the permutation is fixed. We next swap the second element of the
vector with a random element other than the first element. And so on.
It is clear that this produces each permutation with equal probability
--- each of the n elements has an equal chance of going in the first
slot, each of the remaining elements will have an equal chance of
going in the second slot, and so on.

Style comments welcome. Utility macros (I use these in lots of
programs that need to be efficient) are at the end; I normally keep
these in a different package --- make sure they're visible to the
permutation code.

Cheers,

rif

(defpackage :combinatorics
  (:use :common-lisp)
  (:export :random-subset :random-permutation))

(defmethod random-subset ((n fixnum) k)
  "Chooses a k element subset from 0 through n-1.
Results are in a vector of fixnums. The subset
is ordered (i.e. you can get (0 4) or (4 1))."
  (labels ((swap-elts (a i1 i2)
             (psetf (aref a i1) (aref a i2)
                    (aref a i2) (aref a i1))))
    (let ((set (0-n-vec n)))
      (fixtimes (i k)
                (swap-elts set i (+ i (random (- n i)))))
      (ct-typed-vector-subset set 0 k fixnum))))

(defmethod random-subset ((v vector) k)
  (indexed-vector-subset v (random-subset (veclen v) k)))

(defmethod random-permutation ((n fixnum))
  (random-subset n n))

(defmethod random-permutation ((v vector))
  (indexed-vector-subset v (random-permutation (veclen v))))

(defun indexed-vector-subset (v inds)
  (declare (type (simple-array * (*)) v)
           (type (simple-array fixnum (*)) inds))
  (let* ((n (veclen inds))
         (result (typed-array n (array-element-type v))))
    (fixtimes (i n)
       (setf (aref result i) (aref v (aref inds i))))
    result))

;;; From my collection of utilities

(defmacro typed-array (size type &rest rest)
  (let ((size-sym (gensym)))
    `(let ((,size-sym ,size))
      (declare (type fixnum ,size-sym))
      (make-array ,size-sym :element-type ,type ,@rest))))

(defmacro fixtimes ((var count &optional (result nil)) &body body)
  (let ((g (gensym "COUNTER")))
    `(let ((,g (the fixnum ,count)))
      (dotimes (,var ,g ,result)
        (declare (type fixnum0+ ,var))
        ,@body))))

(defmacro ct-typed-vector-subset (orig-vector start end type)
  (with-gensyms (start-sym end-sym orig-sym)
    `(let ((,start-sym ,start)
           (,end-sym ,end)
           (,orig-sym ,orig-vector))
      (declare (type fixnum ,start-sym)
               (type fixnum ,end-sym)
               (type (simple-array ,type (*)) ,orig-sym))
      (let ((length (- ,end-sym ,start-sym))
            (offset ,start-sym))
        (returning (result (typed-array length ',type))
          (fixfor (i 0 length)
            (setf (aref result i) (aref ,orig-sym (+ offset i)))))))))

(defmacro with-gensyms (syms &body body)
  `(let (,@(mapcar (lambda (sy)
                     `(,sy (gensym ,(symbol-name sy))))
                   syms))
    ,@body))

Relevant Pages

  • Re: 1-1/2+1/3-1/4+1/5-1/6+1/7
    ... Let poo be the infinite composition of p with itself. ... is a permutation. ... what is the first element of poo? ...
    (sci.math)
  • Re: 1-1/2+1/3-1/4+1/5-1/6+1/7
    ... Let p the permutation that switches ... Let poo be the infinite composition of p with itself. ... What is the first element of poo? ...
    (sci.math)
  • Re: 1-1/2+1/3-1/4+1/5-1/6+1/7
    ... Let poo be the infinite composition of p with itself. ... is a permutation. ... What is the first element of poo? ...
    (sci.math)
  • Re: 1-1/2+1/3-1/4+1/5-1/6+1/7
    ... Let p the permutation that switches ... Let poo be the infinite composition of p with itself. ... What is the first element of poo? ...
    (sci.math)