From: Yuri Khan <yuri.v.khan@gmail.com>
To: Emanuel Berg <moasenwood@zoho.eu>,
help-gnu-emacs <help-gnu-emacs@gnu.org>
Subject: Re: comic-book-insult
Date: Mon, 9 Sep 2019 12:09:08 +0700 [thread overview]
Message-ID: <CAP_d_8V08ww1UoPktg7B_KZZw5dof2XC4FGfVvTurhGuNmfcJg@mail.gmail.com> (raw)
In-Reply-To: <86k1aiip6o.fsf@zoho.eu>
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
next prev parent reply other threads:[~2019-09-09 5:09 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-09-08 19:05 comic-book-insult Emanuel Berg via Users list for the GNU Emacs text editor
2019-09-08 20:16 ` comic-book-insult Marcin Borkowski
2019-09-08 22:55 ` comic-book-insult Emanuel Berg via Users list for the GNU Emacs text editor
2019-09-08 22:29 ` comic-book-insult Adam Porter
2019-09-10 23:43 ` comic-book-insult Emanuel Berg via Users list for the GNU Emacs text editor
2019-09-08 23:47 ` comic-book-insult Eric Abrahamsen
2019-09-09 3:56 ` comic-book-insult Emanuel Berg via Users list for the GNU Emacs text editor
2019-09-09 5:09 ` Yuri Khan [this message]
2019-09-09 17:41 ` comic-book-insult Emanuel Berg via Users list for the GNU Emacs text editor
2019-09-09 18:26 ` comic-book-insult Yuri Khan
2019-09-09 18:33 ` comic-book-insult Emanuel Berg via Users list for the GNU Emacs text editor
2019-09-09 8:00 ` comic-book-insult Jean Louis
2019-09-09 17:32 ` comic-book-insult Emanuel Berg via Users list for the GNU Emacs text editor
2019-09-09 18:05 ` comic-book-insult Jean Louis
2019-09-09 18:10 ` comic-book-insult Emanuel Berg via Users list for the GNU Emacs text editor
2019-09-09 18:13 ` comic-book-insult Eli Zaretskii
2019-09-11 12:56 ` Anonymous arguments - comic-book-insult Jean Louis
2019-09-11 15:12 ` Emanuel Berg via Users list for the GNU Emacs text editor
2019-09-17 6:19 ` Jean Louis
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAP_d_8V08ww1UoPktg7B_KZZw5dof2XC4FGfVvTurhGuNmfcJg@mail.gmail.com \
--to=yuri.v.khan@gmail.com \
--cc=help-gnu-emacs@gnu.org \
--cc=moasenwood@zoho.eu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.