8 May 2000 Kalana   » (Journeyer)

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...

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!