sample.rb

def array_sample(arr, k)
  rng = Random.new
  sample = Array.new k
  sample[0] = arr[0]
  (1...k).each {|i|
    r = rng.rand(i + 1)
    sample[i] = sample[r]
    sample[r] = arr[i]
  }
  (k...arr.size).each {|i|
    r = rng.rand(i + 1)
    sample[r] = arr[i] if r < k
  }
  sample
end

O(min(arr.size, n)) かもしれないやつ

def array_sample(arr, n)
  replaced = {}
  n.times.map do |i|
    idx = rand arr.size-i
    idx1 = replaced[idx] || idx
    idx2 = arr.size-i-1
    replaced[idx] = replaced[idx2] || idx2
    arr[idx1]
  end
end