Generate a uniformly distributed random number. Iterate through your list until the cumulative probability of the visited elements is greater than the random number Sample code: double p = Math.random(); double cumulativeProbability = 0.0; for (Item item : items) { cumulativeProbability += item.probability(); if (p <= cumulativeProbability) { return item; } }
You are looking to partition the distance from 0 to 1. Choose n – 1 numbers from 0 to 1, sort them and determine the distances between each of them. This will partition the space 0 to 1, which should yield the occasional large result which you aren’t getting. Even so, for large values of … Read more
You are looking for the alias method which provides a O(1) method for generating a fixed discrete probability distribution (assuming you can access entries in an array of length n in constant time) with a one-time O(n) set-up. You can find it documented in chapter 3 (PDF) of “Non-Uniform Random Variate Generation” by Luc Devroye. … Read more
Are the 160 bit hash values generated by SHA-1 large enough to ensure the fingerprint of every block is unique? Assuming random hash values with a uniform distribution, a collection of n different data blocks and a hash function that generates b bits, the probability p that there will be one or more collisions is … Read more
xor is a dangerous default function to use when hashing. It is better than and and or, but that doesn’t say much. xor is symmetric, so the order of the elements is lost. So “bad” will hash combine the same as “dab”. xor maps pairwise identical values to zero, and you should avoid mapping “common” … Read more
The simple solution is to generate a number with a uniform distribution (using rand), and manipulate it a bit: r = rand; prob = [0.5, 0.1, 0.4]; x = sum(r >= cumsum([0, prob])); or in a one-liner: x = sum(rand >= cumsum([0, 0.5, 0.1, 0.4])); Explanation Here r is a uniformly distributed random number between … Read more
If the sampling is with replacement, you can use this algorithm (implemented here in Python): import random items = [(10, “low”), (100, “mid”), (890, “large”)] def weighted_sample(items, n): total = float(sum(w for w, v in items)) i = 0 w, v = items[0] while n: x = total * (1 – random.random() ** (1.0 / … Read more
How to generate a random point within a circle of radius R: r = R * sqrt(random()) theta = random() * 2 * PI (Assuming random() gives a value between 0 and 1 uniformly) If you want to convert this to Cartesian coordinates, you can do x = centerX + r * cos(theta) y = … Read more
There is a built in. from difflib import SequenceMatcher def similar(a, b): return SequenceMatcher(None, a, b).ratio() Using it: >>> similar(“Apple”,”Appel”) 0.8 >>> similar(“Apple”,”Mango”) 0.0