title: Pick N distinct items at random from sequence of unknown length, in only one iteration
body: <p>I am trying to write an algorithm that would <strong>pick N distinct items from an sequence at random, without knowing the size of the sequence in advance, and where it is expensive to iterate over the sequence more than once</strong>. For example, the elements of the sequence might be the lines of a huge file.</p>
  
  <p>I have found a solution when N=1 (that is, "pick exactly one element at random from a huge sequence"):</p>
  
  <pre><code>import random
  items = range(1, 10) # Imagine this is a huge sequence of unknown length
  count = 1
  selected = None
  for item in items:
      if random.random() * count &lt; 1:
          selected = item
      count += 1
  </code></pre>
  
  <p>But how can I achieve the same thing for other values of N (say, N=3)?</p>