I will start with putting function code because it's quite small, and for reference (starting description comment omitted).
/// --- validate general input
#include "..\paramsCheck.inc"
paramsCheck(_this,isEqualType,[])
private _cnt = count _this;
for "_i" from 1 to _cnt do {
_this pushBack (_this deleteAt floor random _cnt);
};
_this
According to BIS_fnc_arrayShuffle:
Now, what's wrong.
As you can see, no new array is created, and instead passed array is shuffled in-place. Function itself fails to shuffle (at least for what I think shuffle is).
What I think shuffle is: all elements of input array get fairly equal chances to appear in any position in output array.
What we have in function?
TL;DR. First elements are less likely to be shuffled than last ones.
Let's say we have array of N elements numbered 0, 1, ... N-1. Fair probability for any element to take any position is 1/N.
Line 24 removes element with random index M (all consequent elements moved one element towards the array front) and pushes it to array's back.
Operation affects positions of elements in range [M, ... N-1] unless M == N-1 (in which case nothing is changed, but delete and insertion performed!).
Position of M elements (numbered 0..M-1) is unchanged. For arbitrary M in [0, 1, ..., N-1] you have the probability (N-M-1)/N that first M elements will remain on their positions after this iteration.
Entire loop lasts N iterations. So the probability of element not being picked up and not moved in entire loop is ((N-M-1)/N)N. Full probability of element to stay on its initial place also includes the cases when element goes to back and after some iterations shifts to its initial place. For 0th element probability of shifting back to 0th position is 1/N * (N-1)/N * (N-2)/N * ... * 1/N = (N-1)!/(NN). For the last exactly 1/N (simply probability of picking specific element; fair for this position, still not fair for others) -- if last element moved to array's back in last iteration.
Assuming that , probability of 0th element staying in 0th position first falls and has minimum in N=5, then grows and asymptotically strives for 1/e, i.e. ~0.367879441, no matter what size array is. When in fact it should be exactly 1/N for any N.
That is, having array of 10 elements, for first element (M=0) you will have probability (10-0-1)/10 = 0.9 (90%) that it stays on its place after first iteration. Probability 0.8 (80%) of that two first elements are not shuffled after first iteration (quite obvious). Probability of first element staying in first position after entire loop is 0.348714728 (~34.8%) when it should be 10%.
Sorry, did not do the maths for other elements, but I think it's enough already to state that shuffle fails.
The easiest way to fix the loop is to rewrite it like this:
for "_i" from 1 to _cnt do {
_this pushBack (_this deleteAt floor random (_cnt+1-_i));
};
Thus not picking any element second time and providing fair 1/N probability for all elements.
However, I don't like this approach because of too many (unnecessary) deletes, causing multiple elements to shift towards array front, meaning worst case complexity of O(n2) (if random always returns 0).
I don't know how arrays work inside. If shifting elements of arbitrary types is quite costly operation (very likely for vector-like containers filled with data structures itself, not pointers), it's better shift numbers (indexes of elements).
Here's my implementation of function, fixing both issues:
/// --- validate general input
#include "..\paramsCheck.inc"
paramsCheck(_this,isEqualType,[])
private ["_cnt", "_result"];
_cnt = count _this;
_result = [];
if (_cnt > 0) then {
private ["_i", "_idxs"];
_idxs = [];
_idxs resize _cnt;
for [{_i = 0}, {_i < _cnt}, {_i = _i + 1}] do {
_idxs set [_i, _i];
};
_result resize _cnt;
for [{_i = 0}, {_i < (_cnt-1)}, {_i = _i + 1}] do {
_result set [_i, _this select (_idxs deleteAt floor random (_cnt-_i))];
};
_result set [_cnt-1, _this select (_idxs select 0)];
};
_result
It does multiple deletes from array too, but at least elements are always numbers.
Whoever wants a fair shuffle, feel free to use.
Having BIS_fnc_sortBy function discovered broken recently, I think there should be some review in arrays functions code. And I'll be digging too, hehe :icon_twisted: I see what you did there, KK
There's hotfix coming soon, I wonder if BIS could fix this function too.
Best regards.