8 May 2000 bucky   » (Apprentice)

Algorithms

andrei, I was just reading Programming Pearls this weekend, and Bentley was working on a very similar problem in chapter 12 (for generating random test examples, I think). Here's hoping I remember it correctly: (pseudo-code, of course)

int num_needed, num_available; /* pre-initialized */
List NewList;
for (element = List->first; 
      element->next != NULL;
      element = element->next) {
    if (@random@number@ < (num_needed/num_available)) {
        append(NewList, element); /* sort of - really just
the data */
        num_needed--;
    }
    num_available--;
}

"@random@number@" and "append" are mostly hand-waving, of course. This should guarantee that you'll get exactly num_needed elements in the new list, and the order from the original list is maintained (I wasn't sure whether that was important, from your posts). And I believe the distribution is uniform, too.

I hope this matches the problem you're working on.

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!