I'm not a math major, but I don't really see an alternative if your probabilities are not predictable in advance. If they are, you can tackle an algorithm without going through the list, but you imply this is not the case.

Here is one idea though. This is off the top of my head, doubtless it needs some refinement:

If your probabilities don't change often, you could pre-sort the list into "chunks" of recorded sizes (but near a target, frex 0.1) which would make your select time near constant to select the correct chunk, then linear inside that chunk (where you have notably fewer items). If your probabilities change often though, this sorting may not be worthwhile.

Example: a b c d e f g h i j with probabilities 0.02, 0.05, 0.20, 0.11, 0.1, 0.14, 0.08, 0.08, 0.09, 0.11)

We can sort this into a data structure like:

[ {
  Total => 0.07,
  Set => [ { a=> 0.02, b => 0.07}]
  },
  { 
  Total => 0.27,
  Set => [ { c => 0.20}]
  },
  { 
  Total => 0.27,  #repeat since it span's two "subsets"
  Set => [ { c=> 0.20 }]
  }, 
  { 
  Total => 0.38,
  Set => [ { d => 0.11 } ] 
  },
  #etc
]
[download]

But again, this sorting will be much more expensive than a single linear search, so you'll have to decide if it's worth it.

If he creates another list of n items listing the cumulative probability to that point, then he can do a binary search. That's more general then the pre-computed "chunks".

use vague;
print some of 1, 2, 3, 4, 5, 6, 7, 8, 9, 10;
print nearly all of "And did those feet in ancient times walk upon Eng
+land's mountains green.";
print hardly any of "And did those feet in ancient times walk upon Eng
+land's mountains green.";
[download]

rdfield

HTH, --traveler

1. Take the sum of all the relative weights and call it N
2. Take a random number between 0 and 1, and multiply it by N. Call the new number X.
3. Iterating through each element of the list do the following:
4. Subtract the weight of the element from X.
5. If X went negative, you are sitting on the chosen element, so quit.
6. Otherwise, move to the next element.

blokhead

my $hash = { 1 => 0.2,
         2 => 0.3,
         3 => 0.5
         };

my $sum;
my $hash2;
while(my($key,$value) = each %{$hash}){
    $sum += $value;
    print "$sum . $key\n";
    $hash2->{$sum} = $key;
}

foreach (1..10){
    my $x =   rand(1);
    print "$x\t";
    foreach (sort { $a <=> $b } keys %{$hash2}){
    if($x < $_){
        print $hash2->{$_},"\n";
        last;
    }
    }
}
[download]

I gather that you're interested in sampling "without replacement" as they say, so the same item can't be drawn twice. If you're only sampling a few items out of hundreds, it may be best to simply reject duplicates. Keep a hash of items you've already selected, and loop until you get a new one. If the probability distribution is highly skewed, or you're taking a large sample, then you're likely to waste a lot of time picking duplicates with this scheme.

The problem is -- this is not very efficient, especially if you have hundreds of items whose probabilities change all the time.

It's often not necessary to actually compute the probability of each item; you can simply work with weights that are proportional to the probability. An item can be effectively removed from the set by setting its weight to zero. The other weights don't need to change.

This thread has a number of good suggestions for the case where the weights do not change. However, if even one of them changes, everything has to be re-examined to update the data structure, at a cost of O(n). I have a solution below which stores the weights in a balanced binary tree instead. Only the ancestors in the tree need to be visited when something is changed, so the cost is O(log n) for a single change. Choosing a random element is O(log n); choosing a sample of k of them is O(k*log n). The code is not terribly pretty, but I think it's fairly efficient. Only the tree-building routine is recursive.

jdporter
The 6th Rule of Perl Club is -- There is no Rule #6.