Problem Statement

This is a method of randomly sampling n items from a set of M items, with equal probability; where M >= n and M, the number of items is unknown until the end. This means that the equal probability sampling should be maintained for all successive items > n as they become available (although the content of successive samples can change).

Note: A class taking n and generating a callable instance/function might also be used.

Let's start with the solution:

KnuthS(v,n)={
  my(u=vector(n,i,i));
  for(i=n+1,#v,
    if(random(i)
  );
  vecextract(v,u)
};
test()={
  my(v=vector(10),t);
  for(i=1,1e5,
    t=KnuthS([0,1,2,3,4,5,6,7,8,9],3);
    v[t[1]+1]++;v[t[2]+1]++;v[t[3]+1]++
  );
  v
};