Re: comic-book-insult

[Yuri Khan]

On Mon, 9 Sep 2019 at 02:05, Emanuel Berg via Users list for the GNU
Emacs text editor <help-gnu-emacs@gnu.org> wrote:

>         (rand-chars (sort chars (lambda (_ __) (zerop (random 2)))))

If you were to pull off this kind of thing in C or C++, that would be
classified as undefined behavior and possibly cause demons to fly out
your nose. The comparison predicate used in sorting algorithms must be
a strict weak ordering, i.e.:

* irreflexive — (not (p x x)) for each x;
* antisymmetric — if (p x y), then (not (p y x));
* transitive — if (p x y) and (p y z), then (p x z);
* the equivalence induced by it must also be transitive — if (not (or
(p x y) (p y x))) and (not (or (p y z) (p z y))), then (not (or (p x
z) (p z x))).

A predicate that returns a random boolean on each invocation will
easily violate any or all of the above.


The canonical lazy coder way to random-shuffle a collection is to
first associate a random value with each element, then sort by that:

(concat
 (seq-map #'car
          (seq-sort-by #'cdr #'<
                       (seq-map (lambda (x) (cons x (random)))
                                (string-to-vector "@#$%&")))))

(This whole sorting approach is criticized because it is O(n log n) in
the number of elements while there exist random shuffle algorithms
that are linear, i.e. O(n). See [1].)

[1]: https://stackoverflow.com/a/1287572/1326190