Re: Add seq-shuffle

[Emanuel Berg <incal@dataswamp.org>]

Philip Kaludercic wrote:

>> That's a neat and concise solution. It seems to produce
>> a decently random sorting, but I'd guess that it may not
>> perform well for large sequences. For example:
>>
>>     (let (comparisons)
>>       (list :result (seq-sort (lambda (a b)
>>                                 (push (cons a b) comparisons)
>>                                 (zerop (random 2)))
>>                               (number-sequence 0 10))
>>             :num-comparisons (length comparisons)))
>>     ;; (:result (6 0 9 1 5 10 8 2 7 3 4) :num-comparisons 26)
>>
>> In testing that expression repeatedly, I see that the
>> number of comparisons varies between about 23 and 26.
>>
>> Thanks for pointing it out, though. It's good to know that
>> it exists and in what circumstances it could be useful.
>
> IIRC the approach is related to the "Naive method" mentioned
> on Wikipedia [0]. I think that this variation of your code
> demonstrates that not all elements are considered equally
> often:
>
>   (let ((comparisons '()))
>     (list :result
>           (seq-sort (lambda (a b)
>                               (cl-incf (alist-get a comparisons 0))
>                               (cl-incf (alist-get b comparisons 0))
>                               (zerop (random 2)))
>                             (number-sequence 0 10))
>           :num-comparisons
>           (seq-sort (lambda (x y)
>                       (< (cdr x) (cdr y)))
>                     comparisons)))
>   ;; (:result
>   ;;  (9 0 1 7 4 10 5 6 8 3 2)
>   ;;  :num-comparisons
>   ;;  ((0 . 2) (10 . 3) (8 . 3) (9 . 4) (7 . 4) (6 . 4) (4 . 5) (2 . 5) (3 . 7) (1 . 7) (5 . 8)))

I think it is as random as `random', as for the exact
execution of the algorithm one should examine 'seq-sort'.

Natural thing would just be to go from one end to the other,
but maybe they do some optimizations.

> While acceptable as a personal hack

Very generous of you, noble sir!

-- 
underground experts united
https://dataswamp.org/~incal