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 20:09:53 +0100 Organization: A noiseless patient Spider Lines: 50 Message-ID: <87czi71abi.fsf@bsb.me.uk> References: <1a628830-6d23-42f9-b6b3-e0132ef3379fn@googlegroups.com> <87wngf1gup.fsf@bsb.me.uk> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: reader02.eternal-september.org; posting-host="0b1bfd64e7a9919f9616c2cd2b028c77"; logging-data="11775"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/ekoVa87raE7Mhs6TTwg4t/1VLhZXtzeo=" Cancel-Lock: sha1:imFyC56MHMYWpxvpAEJdmEfA850= sha1:e5VbSf5aJyFb5G/32YSIHQvkZGo= X-BSB-Auth: 1.926dca0e65710b691440.20220327200953BST.87czi71abi.fsf@bsb.me.uk Xref: csiph.com comp.programming:14751 Ben Bacarisse writes: > 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. 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.