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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)