Re: Add seq-shuffle

[Philip Kaludercic <philipk@posteo.net>]

Adam Porter <adam@alphapapa.net> writes:

> Hi Emanuel,
>
> 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 "Naïve 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)))

While acceptable as a personal hack, it a proper solution should do
Fisher–Yates.  Adding a "shuffle" function to Emacs would also eliminate
the excuse to use suboptimal fallbacks.

[0] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Na%C3%AFve_method

>
> --Adam
>
>

-- 
	Philip Kaludercic on siskin