
[Norvig] Now I'm going to show you this program, test_shuffler,

that produces the output you just saw

to see if a shuffle program is correct, if it comes up with a balanced set of results.

So what am I going to do?

First I'm going to keep track of the counts of every result that comes back from the shuffler.

I'm going to start counts off as a default dictionary.

That means that its default value is the default value of integer, which is 0.

So the counts all start at 0.

And then I go from range(n), so n times,

and by default we're going to go 10000 shuffles.

We're going to make a list out of the deck that we get passed in.

The deck is just a string of characters. That's the simplest thing to show.

Then we're going to shuffle the input and then count the result.

And result here is a list of items.

We're going to join the list of items together back into a single string

to make them smaller and easy to deal with,

and then we just increment that count.

So abcd comes in, we make a list, we make the list abcd,

we shuffle that, maybe we get bcad, and then we increment the count for that result.

Now, we calculate the expected count, what we expect to get,

and that's 1 over the factorial of the number of items in the deck

because all n factorial where n is the length of the deck items are equally probable.

And so the expected count should be n times that.

And then we say that the result is okay if the counts for each item

The ratio of the counts to the expected value should be about 1.

And we're going to say if it's within 0.9 and 1.1 of what we expect, then that's okay.

If any item doesn't have that, then it's not okay.

What we passed in as shuffler is a function,

and functions have a name attribute, so we're pulling out the name of the shuffler

and then we're just printing out the name of the shuffler, the deck we're shuffling,

and whether it's okay or not,

and then we print out the individual probabilities for each of the possible results.

And then I made another function, test_shufflers,

which takes a list of shufflers and a list of possible decks

and it applies the test to the cross product of them.

For every shuffler we test every deck and we print the result.

We saw that the function shuffle1 was not a good function,

so I'm trying to fix it up, and I have 2 attempts here called shuffle2 and shuffle3.

We can see what's going on here.

In shuffle2 it's almost the same as shuffle1,

except when I pick out 2 random indices to swap,

I'm only saying that swapped of i is true,

and I'm not saying that swapped of j is true.

Otherwise it's the same.

In shuffle3 I go through the deck.

Rather than have a while loop, I just go through the deck for each of the indices

and swap that index with something in the random range of N.

So in other words, we swap each of the elements in the deck

with any one of the other elements.