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

Groups > comp.programming > #14750

Re: Partial shuffle

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

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