* Re: shuffle array
[not found] ` <CAN=4vMpt+hQw2zxUC1LH+3bPymBX_5qqexFw-vqkN6ye+dG1ZQ__45487.0572009654$1575297047$gmane$org@mail.gmail.com>
@ 2019-12-02 15:16 ` Stephane Chazelas
2019-12-02 15:27 ` Roman Perepelitsa
0 siblings, 1 reply; 3+ messages in thread
From: Stephane Chazelas @ 2019-12-02 15:16 UTC (permalink / raw)
To: zsh-workers
2019-12-02 15:29:17 +0100, Roman Perepelitsa:
> Another alternative is to implement the standard inplace shuffle
> algorithm from scratch:
>
> local -i i
> for ((i = 2; i <= $#l; ++i)); do
> local j=$((RANDOM % i + 1))
shouldn't that be "RANDOM % $#l + 1"?
> # swap l[i] and l[j]
> local tmp=$l[i]
> l[i]=$l[j]
> l[j]=$tmp
> done
>
> Due to RANDOM having a rather narrow range, this will introduce bias
> on large arrays and won't work at all on arrays with more than 32k
> elements. These issues can be mitigated by replacing RANDOM with
> (RANDOM << 15 | RANDOM) or even with (RANDOM << 30 | RANDOM << 15 |
> RANDOM).
[...]
Or use rand48() in zsh/mathfunc
((j = 1 + rand48() * $#l))
--
Stephane
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: shuffle array
2019-12-02 15:16 ` shuffle array Stephane Chazelas
@ 2019-12-02 15:27 ` Roman Perepelitsa
0 siblings, 0 replies; 3+ messages in thread
From: Roman Perepelitsa @ 2019-12-02 15:27 UTC (permalink / raw)
To: Stephane Chazelas; +Cc: Zsh hackers list
On Mon, Dec 2, 2019 at 4:21 PM Stephane Chazelas
<stephane.chazelas@gmail.com> wrote:
> shouldn't that be "RANDOM % $#l + 1"?
No, the original code is correct. There is a loop invariant that
l[1,i-1] is shuffled before each iteration. An iteration makes l[1,i]
shuffled.
It's fairly easy to prove that this algorithm will produce each array
permutation with equal probability (assuming that we have access to a
function that gives a random number from [1, N] with uniform
distribution.)
> Or use rand48() in zsh/mathfunc
Thanks, TIL.
Roman.
^ permalink raw reply [flat|nested] 3+ messages in thread
[parent not found: <867e3jxtao.fsf__7557.99096530012$1574997710$gmane$org@zoho.eu>]
end of thread, other threads:[~2019-12-02 15:28 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <867e3jxtao.fsf@zoho.eu>
[not found] ` <20191129064215.GA14095@prometheus.u-strasbg.fr>
[not found] ` <8636e7w0w9.fsf__36104.0529723809$1575015640$gmane$org@zoho.eu>
[not found] ` <20191201200719.anzbs27c7phgdnmm@chaz.gmail.com>
[not found] ` <20191201233848.7selcpkvenlu65px__33142.5388505281$1575243619$gmane$org@tarpaulin.shahaf.local2>
[not found] ` <20191202141421.sj7nlhsdrpqxpr42@chaz.gmail.com>
[not found] ` <CAN=4vMpt+hQw2zxUC1LH+3bPymBX_5qqexFw-vqkN6ye+dG1ZQ__45487.0572009654$1575297047$gmane$org@mail.gmail.com>
2019-12-02 15:16 ` shuffle array Stephane Chazelas
2019-12-02 15:27 ` Roman Perepelitsa
[not found] <867e3jxtao.fsf__7557.99096530012$1574997710$gmane$org@zoho.eu>
2019-12-01 19:57 ` Stephane Chazelas
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/zsh/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).