sample.jl

function rand_first_index(n, k)
    r = rand()
    p = k/n
    i = 1
    while p < r
        i += 1
        p += (1-p)k/(n-(i-1))
    end
    return i
end

function ordered_sample_norep!(xs::AbstractArray, target::AbstractArray)
    n = length(xs)
    k = length(target)
    i = 0
    for j in 1:k
        step = rand_first_index(n, k)
        n -= step
        i += step
        target[j] = xs[i]
        k -= 1
    end
    return target
end