Re: Partial shuffle

Path	csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.programming
Subject	Re: Partial shuffle
Date	Sun, 27 Mar 2022 17:48:46 +0100
Organization	A noiseless patient Spider
Lines	44
Message-ID	<87wngf1gup.fsf@bsb.me.uk> (permalink)
References	<1a628830-6d23-42f9-b6b3-e0132ef3379fn@googlegroups.com>
Mime-Version	1.0
Content-Type	text/plain
Injection-Info	reader02.eternal-september.org; posting-host="0b1bfd64e7a9919f9616c2cd2b028c77"; logging-data="24254"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18vF4MbfDxKNvCCY0wyFLGIeyVDiYO6dbc="
Cancel-Lock	sha1:ZFHCBdPE2IRHclK4KAv8kWpTcv8= sha1:Hf3T+a9shmaquc4YpDOPBdEIdZI=
X-BSB-Auth	1.ff765d828f02ff54969e.20220327174846BST.87wngf1gup.fsf@bsb.me.uk
Xref	csiph.com comp.programming:14750

Show key headers only | View raw

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> You have a list of candidates, ranked by score. You want to try them
> out in order, with the better candidates being tried first. However
> you don't want the process to be deterministic - each run should yield
> a separate order. And you want even low-ranked candidates to have some
> chance of being tried early.
>
> Is there a partial sort / partial shuffle which can achieve this?

Let me check is I know what you mean.  You have a list of words with
scores

  12 apple
  10 cat
   9 dog
   8 egg
   5 fox

and you want a quasi-sort that might just (but very very rarely)
produce

   5 fox
   8 egg
   9 dog
  10 cat
  12 apple

but will produce these orderings much more frequently:

  12 apple    10 cat       10 cat
   9 dog       9 dog       12 apple
  10 cat      12 apple      8 egg      
   8 egg       8 egg        5 fox
   5 fox       5 fox        9 dog

?  First thought.  Have a random field, r, that is chosen from a normal
distribution prior to each sort.  Then sort by score+r.  By adjusting
the distribution's parameters, you will get different probabilities of
re-arrangement from almost none (with, say, mean=0, sdev=0.1) to chaotic
when mean=1000 sdev=10000.

-- 
Ben.

Thread

Partial shuffle Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-03-26 15:28 -0700
  Re: Partial shuffle Richard Heathfield <rjh@cpax.org.uk> - 2022-03-27 10:19 +0100
  Re: Partial shuffle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-03-27 17:48 +0100
    Re: Partial shuffle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-03-27 20:09 +0100
      Re: Partial shuffle Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-03-27 12:19 -0700
  Re: Partial shuffle Paul N <gw7rib@aol.com> - 2022-03-28 14:12 -0700

csiph-web