Algorithms For Dummies

  Using Randomized Algorithms 

     327

to avoid picking a series of bad numbers. This is the strategy used by the Quickse-

lect and randomized Quicksort algorithms, described later in the chapter.

Because  algorithms  need  numeric  inputs,  knowing  their  distribution  can  help 

make them work smarter. It’s not just the initial distribution that counts. You can 

also take advantage of how data distribution changes as the algorithm proceeds. 

As an example of how a changing distribution can improve your algorithm, the 

following code shows how to guess a card in a French deck by random choice:

numbers = ['Ace','2','3','4','5','6','7','8','9','10',

                                'Jack','Queen','King']

seeds = ['Clubs','Spades','Diamonds','Hearts']

deck = [s

+'_'+n for n in numbers for s in seeds]

from random import choice

my_cards = deck.copy()

guessed = 0

for card in deck:

    if card == choice(my_cards):

        guessed 

+= 1

print ('Guessed %i card(s)' % guessed)

Guessed 1 card(s)

This strategy brings few results, and on average, you’ll guess a single card in all 

52 trials. In fact, for each trial, you have a 1/52 probability of guessing the correct 

FIGURE 17-2: 

A histogram  

of a uniform 

distribution.

---

328

 

   

  PART 5