<p>When N is very large, the normal method that randomly shuffles the N numbers and selects, say, first k numbers, can be prohibitive because of space complexity. The following algorithm requires only O(k) for both time and space complexities.</p>

<p><a href="http://arxiv.org/abs/1512.00501" rel="nofollow">http://arxiv.org/abs/1512.00501</a></p>

<pre><code>def random_selection_indices(num_samples, N):
    modified_entries = {}
    seq = []
    for n in xrange(num_samples):
        i = N - n - 1
        j = random.randrange(i)

        # swap a[j] and a[i] 
        a_j = modified_entries[j] if j in modified_entries else j 
        a_i = modified_entries[i] if i in modified_entries else i

        if a_i != j:
            modified_entries[j] = a_i   
        elif j in modified_entries:   # no need to store the modified value if it is the same as index
            modified_entries.pop(j)

        if a_j != i:
            modified_entries[i] = a_j 
        elif i in modified_entries:   # no need to store the modified value if it is the same as index
            modified_entries.pop(i)
        seq.append(a_j)
    return seq
</code></pre>
Select N random elements from a List<T> in C#
<p>I need a quick algorithm to select 5 random elements from a generic list. For example, I'd like to get 5 random elements from a <code>List&lt;string&gt;</code>.</p>