Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #14751

Re: Partial shuffle

Show all headers | 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.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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