Выбор случайного элемента из массива в Ruby ONCE ONLY

Question

Я знаю, что я могу выбрать случайный элемент из массива с помощью метода образца, но это оставляет возможность выбора элемента более одного раза. Сначала я мог сначала перетасовать массив, а затем перейти от первого к последнему элементу по порядку, но я понимаю, что это интенсивный процесс памяти, и я ищу менее интенсивный метод, если это возможно!

Answer 1

Шаркая массив не большой объем памяти. Ruby имеет стандартную реализацию тасования по умолчанию, она называется Array.shuffle!. Глядя на исходный код для этого вы можете увидеть (это 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; 
} 

Эта реализация следует классический Fisher-Yates algorithm.

Итак:

1. Перемешать массив на месте с помощью shuffle!. Сложность времени - O(n), дополнительной памяти не требуется.
2. Итерации над массивом. Сложность времени - O(n), дополнительная память не требуется (только целое число для хранения текущего индекса).

В целом у вас есть то, что вам нужно без дополнительной памяти и временной сложности O(n).

Answer 2

Вы должны отслеживать те элементы, которые вы уже выбрали; что вы собираетесь делать, поместите их в свой собственный массив?

Shuffle and iterate. Это не занимает больше памяти, чем отслеживание уже выбранных элементов.

Answer 3

Если элементы массива действительно очень большой, то можно попробовать просто перетасовать список индексов и перебирать, что:

a = %w{a b c d e f g h} 

[*0...a.size].shuffle.each do |index| 
    puts a[index] 
end 

Answer 4

sample принимает аргумент:

[*(1..10)].sample(5) #=>[3, 4, 1, 8, 9] 

Ни один элемент не будет выбран в два раза.