ruby - Rubyの配列からランダムな要素を1回だけ選択する

Question

サンプルメソッドを使用して配列からランダムな要素を選択できることはわかっていますが、これにより、要素が複数回選択される可能性が残ります。最初に配列をシャッフルしてから、最初から最後の要素に順番に移動することもできますが、これはメモリを大量に消費することを理解しており、可能であれば、より集中度の低い方法を探しています。

Answer 1

sample引数を取る：

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

要素が2回選択されることはありません。

Answer 2

配列をシャッフルすることは、メモリを大量に消費しません。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;
}

この実装は、古典的なフィッシャー-イェーツアルゴリズムに従います。

それで：

1. を使用して、アレイを所定の位置にシャッフルしshuffle!ます。時間の複雑さはO(n)、余分なメモリは必要ありません。
2. アレイを繰り返し処理します。時間計算量はO(n)、余分なメモリは必要ありません（現在のインデックスを保持するための整数のみ）。

全体として、余分なメモリや時間の複雑さなしに、必要なものがありますO(n)。

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

すでに選択した要素を追跡する必要があります。あなたは何をするつもりですか、それらを彼ら自身の配列に入れますか？

シャッフルして繰り返します。これは、すでに選択されている要素を追跡するよりも多くのメモリを必要としません。