Re: shuffle array

Re: shuffle array

[Stephane Chazelas]

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

Re: shuffle array

[Roman Perepelitsa]

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.

Re: shuffle array

[Stephane Chazelas]

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