Better implementation of random_permutation

Hmm, this is the same Knuth shuffle expressed in a different way,
right? If so the only problem I see is that the random numbers should
come from Maxima's $RANDOM and not CL RANDOM (so that random_permutation
respects the seed the user sets, if any).

Thanks for taking a look at it --

Robert Dodier

On 1/20/11, Mark H Weaver <mhw at netris.org> wrote:
>> The code for random_permutation is in maxima/src/nset.lisp:
>>
>>   (defun $random_permutation (a)
>>     (if ($listp a)
>>       (setq a (copy-list (cdr a)))
>>       (setq a (copy-list (require-set a "$random_permutation"))))
>>
>>     (let ((n (length a)))
>>       (dotimes (i n)
>>         (let
>>           ((j (+ i ($random (- n i))))
>>            (tmp (nth i a)))
>>           (setf (nth i a) (nth j a))
>>           (setf (nth j a) tmp))))
>>
>>     `((mlist) , at a))
>
> Note that the implementation above is quite slow, O(n^2).
> Here's a much faster O(n) version:
>
>   (defun $random_permutation (arg)
>     (let* ((lst (if ($listp arg)
>                     (cdr arg)
>                   (require-set arg "$random_permutation")))
>            (a (make-array (length lst))))
>       (loop for x in lst
>             and i from 0
>             do (shiftf (svref a i)
>                        (svref a (random (1+ i)))
>                        x))
>       (cons '(mlist)
>             (loop for x across a
>                   collect x))))
>
> On my system (Maxima 5.23.2 on GCL 2.6.7 on a Loongson processor),
> this version runs about 46 times faster on a list of length 1000.
>
> Any objections to me committing this change to the trunk?
>
>       Mark
>
>
> PS: here's equivalent pseudo-code for the new version:
>
>   random_permutation(array b)
>   {
>       n <-- length(b);
>       a <-- new_array(n);
>       for i from 0 to n-1 do
>       {
>           j    <-- random integer (such that 0 <= j <= i);
>           a[i] <-- a[j];
>           a[j] <-- b[i];
>       }
>       return(a);
>   }
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>