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 20:09:53 +0100
Organization	A noiseless patient Spider
Lines	50
Message-ID	<87czi71abi.fsf@bsb.me.uk> (permalink)
References	<1a628830-6d23-42f9-b6b3-e0132ef3379fn@googlegroups.com> <87wngf1gup.fsf@bsb.me.uk>
Mime-Version	1.0
Content-Type	text/plain
Injection-Info	reader02.eternal-september.org; posting-host="0b1bfd64e7a9919f9616c2cd2b028c77"; logging-data="11775"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/ekoVa87raE7Mhs6TTwg4t/1VLhZXtzeo="
Cancel-Lock	sha1:imFyC56MHMYWpxvpAEJdmEfA850= sha1:e5VbSf5aJyFb5G/32YSIHQvkZGo=
X-BSB-Auth	1.926dca0e65710b691440.20220327200953BST.87czi71abi.fsf@bsb.me.uk
Xref	csiph.com comp.programming:14751

Show key headers only | View raw

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> 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.

First thought was too fast!  You don't really need to change the mean.
0 will do just fine.  Changing the standard deviation will change the
degree of mixing.

-- 
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