Programming Pearls: How to Random?

Notes for Programming Pearls: second edition , chapter 12, trying to remember the process to solve a problem.

---

They want to automating the task of drawing a random sample from a printed list of precincts.

The input consists of a list of precinct names and an integer m. The output is a list of m of the precincts choosen at random. There are usually a few hundred precinct names( each a string of at most a dozen characters), and m is typically between 20 and 40.

Problem definition

In order to make problem easier to understand and solve, we can make description more abstract.

The input consists of two integers m and n, with m < n. The output is a sorted list of m random integers in the range [0, n-1} in which no integer occurs more than once. For probability buffs, we desire a sorted selection without replacement in which each selection occurs with equal probability.

One solution

Author give us an algorithm from Knuth

select = m
remaining = n
for i = [0, n)
    if (bigrand() % remaining) < select
        print i
        select--
    remaining--

Design space

In order to prepare to solve the tomorrow’s problem, author want us to solve this problem differently.

Set based

One solution we can easily come up with is to produce random number and remove duplicate until we find m different numbers. And set is the common solution for remove duplicates.

while(set.size() < m) {
    random = getRandom()
    if(!set.contain(random)) {
        set.add(random)
    }
}

Faster – less random number

Using the set-based solution has an obvious defect that when m is coming close to n, we will discard many random number which will waste some time.
The following is the algorithm composed by Bob Floyd which will not discard any random number:

for(int j = n - m; j < n; j++) {
    t = ranint();
    if !set.contain(t)
        set.insert(t)
    else 
        set.insert(j)

Another approach – shuffle

Let’s think in another dimension: we don’t generate random number, we shuffle the input and choose first m numbers. So I come up with the following solution with $O(m)$ space.

a = [0..m-1]
select = 0
while select < m
    i = ranint()
    if i < m
        swap(a, select, i)
    else
        a[select] = i
    select++

More to think

The function we have seen so far offer several different solutions to the problem, but they by no means cover the design space. Suppose, for instance, that n is a million and m is n - 10. We might generate a sorted random sample of 10 elements, and then report the integers that aren’t there. Next, suppose that m is ten million and n is 2**31. We could generate eleven million integers, sort them, scan through to remove duplicates, and then generate a ten-million-element sorted sample of that.

Upper words inspire me much:

• to keep mind open – not be limited by old solution, think again about new way to solve it;
• to solve problem according to its condition – not be limited by old problem, this problem is always different;

Written with StackEdit.