Picking random element from an array in Ruby ONCE ONLY

arrays, random, ruby, sample, shuffle

Solution

Shuffling an array is not memory intensive. Ruby has a default in place shuffle implementation, it's called `Array.shuffle!`. Looking at the source code for this you can see (it's C):

rb_ary_shuffle_bang(ary)
    VALUE ary;
{
    long i = RARRAY(ary)->len;

    rb_ary_modify(ary);
    while (i) {
        long j = rb_genrand_real()*i;
        VALUE tmp = RARRAY(ary)->ptr[--i];
        RARRAY(ary)->ptr[i] = RARRAY(ary)->ptr[j];
        RARRAY(ary)->ptr[j] = tmp;
    }
    return ary;
}

This implementation follows the classic Fisher-Yates algorithm.

So:

- Shuffle the array in place using `shuffle!`. Time complexity is `O(n)`, no extra memory needed.

- Iterate over the array. Time complexity is `O(n)`, no extra memory needed (only an integer to hold the current index).

Overall you have what you need with no extra memory and time complexity `O(n)`.

Problem

I know I can pick a random element out of an array with the sample method but this leaves the possibility of an element being picked more than once. I could shuffle the array first and then go from first to last element in order but I understand this is memory intensive and I am looking for a less intensive method if possible!

Original source