English subtitles

← Good Shuffle Solution - Design of Computer Programs

Get Embed Code
1 Language

Showing Revision 3 created 05/25/2016 by Udacity Robot.

  1. [Norvig] And the correct answer is that there would be no error. It would still be fair.
  2. Each permutation of the deck would occur with equal probability,
  3. but it would take N divided by N - 1 times longer--just a tiny bit longer.
  4. We can see that what's happening here is if you remember what our deck looked like,
  5. when we got to the second to last element,
  6. we swapped the second to last element with a random selection from the last 2,
  7. so that's up to N - 1.
  8. If we changed the range to go all the way to N, then we would do 1 more step
  9. where we would swap the last element with an item in the range of just the last element.
  10. So swapping the last element with itself--that would be the only choice--
  11. that wouldn't really do anything effective.
  12. It wouldn't hurt. It would just take a little bit longer.
  13. And so to avoid that redundant operation, we'd use N - 1 rather than N.