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

Groups > comp.programming > #14748 > unrolled thread

Partial shuffle

Back to article view | Back to comp.programming

Contents

  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

#14748 — Partial shuffle

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?

(The application is a crossword grid filler. I score the words, then try to fit them into the grid. But I want a different grid each time, and I don't want it to be too obvious that words with uncommon letters are never chosen.)

[toc] | [next] | [standalone]

#14749

On 26/03/2022 10:28 pm, Malcolm McLean wrote:
> 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?
> 
> (The application is a crossword grid filler. I score the words, then try to fit them into the grid. But I want a different grid each time, and I don't want it to be too obvious that words with uncommon letters are never chosen.)

The obvious way is to change the score by awarding a pseudo-random 
number of bonus points to the low rankers, maybe large to begin with but 
reducing it as the fit proceeds so that it doesn't get tried too often.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#14750

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.

[toc] | [prev] | [next] | [standalone]

#14751

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.

[toc] | [prev] | [next] | [standalone]

#14752

On Sunday, 27 March 2022 at 20:09:56 UTC+1, Ben Bacarisse wrote:
> Ben Bacarisse <ben.u...@bsb.me.uk> writes: 
> 
> > Malcolm McLean <malcolm.ar...@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. 
> 
My thinking was on the lines of sorting the list, then doing a shuffle.
However instead of using a uniform distribution to pick the element
to swap with, us a triangular one, or  a triangle on top of a rectangle.
The distribution is at a maximum at 0 and at a minimum at 1.0.

That avoids needing to add a field. Also, it's maybe easier to control.

[toc] | [prev] | [next] | [standalone]

#14753

On Saturday, March 26, 2022 at 10:28:43 PM UTC, Malcolm McLean wrote:
> 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? 
> 
> (The application is a crossword grid filler. I score the words, then try to fit them into the grid. But I want a different grid each time, and I don't want it to be too obvious that words with uncommon letters are never chosen.)

You could add the scores, pick a number from 1 to that total, and pick as your first candidate the one at that position. Repeat the process for the remaining candidates to pick your second candidate, etc. You could add some sort of scaling to the scores to bias it more in favour of the high-scoring candidates, eg raise all the scores to a power.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web