I think I have another solution to andrei's random elements from a linked list thing.. It's actually pretty similar to Ankh's solution, but you don't need to makeAscendingSequenceOfRandomNumbers, and it has the same restriction that you need to know the number of items, and order doesn't matter. I'm not quite sure mine works though.

When you have a list of n elements and want to pick m, you want each element to have a probablilty m/n of being picked. Walking the list and picking elements where each element's probability of being picked is m/n doesn't work, because you're not guaranteed to end up with m elements.

However, if you pick the first element (with probability m/n), you've changed the problem to picking m-1 elements out of the remaining list of size n. And if you don't pick the first element, you've changed the problem to picking m elements out of the remaining list of size n-1. Pseudocode, recursive:

pickFromList(list L,
             int nWanted,  /* number of elements you want to pick */
             int nItems)  /* size of the list */
{
  if(nWanted == 0){
    return;
  }else if(nWanted == nItems){
    pick every element in L;
  }else{
    if(drand48() < nWanted/nItems){ /* drand48 gives Uniform(0.0, 1.0) */
      pick(L->data);
      pickFromList(nWanted-1, nItems-1, L->next);
    }else{
      pickFromList(nWanted, nItems-1, L->next);
    }
  }
}

Pseudocode, iterative:

pickFromList(list L, int nWanted, int nItems)
{
  int nPicked, nSeen;
  nPicked=0;
  for(nSeen=0, p = L; p != NULL; p = p->next, nSeen){
    if(drand48() < (nWanted-nPicked)/(nItems-nSeen))
      pick(p);
      nPicked++;
    }
  }
}
(probably a few off by ones in there)

Handwaving to show that the above works:
pick 2 out of list of 5 elements: a, b, c, d, e

ac = the event that a is chosen
bc = the event that b is chosen
etc.
A = probability that a is chosen
B = probability that b is chosen
etc.

A = 2/5

B = 1/4 if ac      = 1/4 * 2/5 + 2/4 * 3/5 = 2/20 + 6/20 = 2/5
    2/4 if !ac

P(a chosen   &   b chosen) = P(bc  if ac)  * A     = 1/4 * 2/5 = 2/20
P(a chosen   & ! b chosen) = P(!bc if ac)  * A     = 3/4 * 2/5 = 6/20
P(! a chosen &   b chosen) = P(bc  if !ac) * (1-A) = 2/4 * 3/5 = 6/20
P(! a chosen & ! b chosen) = P(!bc if !ac) * (1-A) = 2/4 * 3/5 = 6/20

C = 0 if   ac  & bc     = 0            = 2/5
    1/3 if ac  & !bc     + 6/20 * 1/3
    1/3 if !ac & bc      + 6/20 * 1/3
    2/3 if !ac & !bc     + 6/20 * 2/3

etc...