* Re: shuffle array [not found] <867e3jxtao.fsf__7557.99096530012$1574997710$gmane$org@zoho.eu> @ 2019-12-01 19:57 ` Stephane Chazelas 0 siblings, 0 replies; 3+ messages in thread From: Stephane Chazelas @ 2019-12-01 19:57 UTC (permalink / raw) To: zsh-workers 2019-11-29 04:20:15 +0100, Emanuel Berg: > How do I shuffle an array? > > I found [1] but it seems like a lot of code? > Not that that's a problem if that's the way > it is. [...] You can do something like: array=(/(Ne['reply=("$array[@]")']oe['REPLY=$RANDOM'])) Though that's a bit convoluted. -- Stephane ^ permalink raw reply [flat|nested] 3+ messages in thread
[parent not found: <867e3jxtao.fsf@zoho.eu>]
[parent not found: <20191129064215.GA14095@prometheus.u-strasbg.fr>]
[parent not found: <8636e7w0w9.fsf__36104.0529723809$1575015640$gmane$org@zoho.eu>]
[parent not found: <20191201200719.anzbs27c7phgdnmm@chaz.gmail.com>]
[parent not found: <20191201233848.7selcpkvenlu65px__33142.5388505281$1575243619$gmane$org@tarpaulin.shahaf.local2>]
[parent not found: <20191202141421.sj7nlhsdrpqxpr42@chaz.gmail.com>]
[parent not found: <CAN=4vMpt+hQw2zxUC1LH+3bPymBX_5qqexFw-vqkN6ye+dG1ZQ__45487.0572009654$1575297047$gmane$org@mail.gmail.com>]
* 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 ` 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
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__7557.99096530012$1574997710$gmane$org@zoho.eu> 2019-12-01 19:57 ` shuffle array Stephane Chazelas [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 ` Stephane Chazelas 2019-12-02 15:27 ` Roman Perepelitsa
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).