Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.programming Subject: Re: Partial shuffle Date: Sun, 27 Mar 2022 17:48:46 +0100 Organization: A noiseless patient Spider Lines: 44 Message-ID: <87wngf1gup.fsf@bsb.me.uk> References: <1a628830-6d23-42f9-b6b3-e0132ef3379fn@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: reader02.eternal-september.org; posting-host="0b1bfd64e7a9919f9616c2cd2b028c77"; logging-data="24254"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18vF4MbfDxKNvCCY0wyFLGIeyVDiYO6dbc=" Cancel-Lock: sha1:ZFHCBdPE2IRHclK4KAv8kWpTcv8= sha1:Hf3T+a9shmaquc4YpDOPBdEIdZI= X-BSB-Auth: 1.ff765d828f02ff54969e.20220327174846BST.87wngf1gup.fsf@bsb.me.uk Xref: csiph.com comp.programming:14750 Malcolm McLean 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.