zsh-workers
 help / color / Atom feed
* 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

* 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

* 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

end of thread, back to index

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

zsh-workers

Archives are clonable: git clone --mirror http://inbox.vuxu.org/zsh-workers

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://inbox.vuxu.org/vuxu.archive.zsh.workers


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git