Array Randomizer function

đź’ˇ Ideas
1

I would like to have an Array Randomizer function, which will return a new randomized array of the given array. Something like,

let array = [1, 2, 3, 4]
array.randomize()
//returns a randomized array
//e.g. [3, 2, 1, 4]
3 Likes
2

You can define this yourself if you need it:

function randomize(array) {
  return array
    .map(v => ({ v, random: Math.random() }))
    .sort(({a: random}, {b: random}) => a - b)
    .map(({v}) => v);
}

randomize([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
// [3, 6, 11, 5, 10, 1, 2, 8, 7, 9, 4]

EDIT: this post is to try and help anyone who is looking for this functionality while there is not a standardized method offering it.

3

That is not guaranteed to give you a random order (though it usually will in practice).

3 Likes
4

Yeah, I have done this before. But I was thinking to have this natively. It will be so useful, specially for beginners who don't know how to do it themselves.

5

Because the pseudo random sequence could be monotonically increasing?

6

@SunPodder : Very good idea!
@aclaymore : All existing methods could be defined by ourselves if/when we need them; then what is the purpose of their existence? Maybe to make our lives easier, to be natively standardized, to be natively optimized, ...?

Method could optionally receive a randomizing function as an option.

2 Likes
7

Yes there are benefits to having functionality built into the language. I completely agree. While something is not available directly in the language it can be helpful to have an example of how to achieve this in userland for people needing a solution and do not have time to wait for a standardized version. I hope that clears up the intention of my original post :slightly_smiling_face:

8

Thanks for appreciating.
Could you be a champion to propose this? Or please help to find a champion to propose this idea.

9

Because the spec gives no guarantees when the comparison function is not consistent, which means that an implementation is allowed to e.g. just leave the array alone once it notices the inconsistency.

10

@bakkot - in @aclaymore's implementation, the comparison function will always be consistent. The first .map() assigns each entry a random id. Once that happens, the .sort() will always sort that array in the exact same way, on any platform. If, instead, the random number was generated inside the sort callback, then we would have a problem, and it wouldn't be a true shuffle.

4 Likes
11

Oh, yeah, I should've read more carefully.

1 Like
12

Sorting does carry hazards, though: Fisher–Yates shuffle - Wikipedia

2 Likes
13

Again, @aclaymore's solution is not the naive "sort with a random comparator result", but rather "give each item a random index and then sort by that", which does work correctly. The only potential hazard, as the Wikipedia article notes, is that if there are random-value collisions in the list they might retain their original order when brought together. But that's not a problem in practice with Math.random() and the sorts of lists you're generally going to be shuffling like this.

2 Likes
14

@tabatkins - I believe the real issue with any shuffling algorithm, is that last paragraph from Wikipedia titled "Pseudorandom generators". I don't know how engines implement Math.random(), but as Wikipedia warns, if the engine only uses a 32 bit seed (or space to store the internal state of the PRNG), then it wouldn't even be capable of shuffling a 52-length array of playing cards. The size of an array that you can really shuffle will always be severely limited if you're using a PRNG.

I wouldn't be surprised if engines use a state size that's bigger than 32 bits, but people will always be trying to shuffle datasets that's larger than what the PRNG algorithm can handle.

Update:

I believe this is all the more reason why shuffling should be a native function. If we care about the issue that Wikipedia is warning about, then it's our job to warn the people using the shuffle function about this pitfall, instead of having everyone handroll their own, without them being aware of this major pitfall.

For example.

> arrayOfSize8.shuffle() // Works
> arrayOfSize100.shuffle() // Error! Array size too large for this shuffling algorithm.
> arrayOfSize100.shuffle({ allowLowRandomness: true }) // Works
3 Likes
15

If the approach “works” or not more depends on why the list is being shuffled.

While the number of states the PRNG has limits how many of the list permutations can be generated. An array of 32 items has 32! permutations so it is unlikely that someone is shuffling it and hoping to see all of those permutations, as that program would take a very long time to run.

I would imagine that for many applications an approximate shuffle is more than sufficient. And implementing this method natively wouldn’t necessarily avoid the PRNG issue as it could end up using the same source of randomness that Math.random uses.

I checked lodash.shuffle - npm and it uses Fisher-Yates.

2 Likes
16

Yeah, virtually zero cases in the real world outside of cryptographic functions need those sort of assurances. A 32-bit PRNG is just fine for shuffling a deck of cards, we don't need :calculates, spits out drink: 226 bits of state

6 Likes