## Bad Shuffle - Design of Computer Programs

• 0:00 - 0:05
[Norvig] Now, by all means, you should use the library functions like random.shuffle.
• 0:05 - 0:07
That's what they're there for.
• 0:07 - 0:09
But I'm going to allow a little bit of a diversion here
• 0:09 - 0:13
because the shuffle algorithm is one that's important to me personally.
• 0:13 - 0:19
It was the first nontrivial algorithm that I came up with on my own when I was in high school
• 0:19 - 0:24
and one of the first cases where I saw that my teacher was just completely wrong.
• 0:24 - 0:29
Here's the algorithm that my teacher was trying to describe to me.
• 0:29 - 0:34
Of course, I went to high school in the Dark Ages before there was any Python,
• 0:34 - 0:36
so it wasn't written in exactly this language,
• 0:36 - 0:39
but I've translated it into Python to make sense to you.
• 0:39 - 0:41
Here's what the algorithm does.
• 0:41 - 0:46
It says we're going to keep track with an array of which items have been swapped so far,
• 0:46 - 0:50
and then until they've all been swapped at least once,
• 0:50 - 0:55
we're going to generate 2 random indices into that array and then swap them
• 0:55 - 0:58
and record the fact that they were both swapped
• 0:58 - 1:02
and keep going until all the items have been swapped at least once.
• 1:02 - 1:04
So it looks like this.
• 1:04 - 1:08
Again, we have this deck of cards
• 1:08 - 1:13
and then we have a parallel array of the same length
• 1:13 - 1:15
which tells us whether we've been swapped or not,
• 1:15 - 1:20
and that starts out as being all false, while this one starts out being cards.
• 1:20 - 1:23
And then we go through and we pick out random numbers.
• 1:23 - 1:31
So say we pick out I and J as being here and here,
• 1:31 - 1:33
and say we have a 9 of diamonds there.
• 1:33 - 1:35
Then we're going to just swap the 2.
• 1:35 - 1:37
And so we cross those out.
• 1:37 - 1:43
We now have the 7 of spades there and the 9 of diamonds there,
• 1:43 - 1:45
and we mark the 2 spots as being swapped.
• 1:45 - 1:49
So now this one is true and this one is true.
• 1:49 - 1:53
Those 2 spots have been swapped, and then we keep on going
• 1:53 - 1:58
until all the elements of swapped are all equal to true. Then we know we're done.
• 1:58 - 2:02
So that's what my teacher was trying to sell to me that day in high school.
• 2:02 - 2:06
I was sitting in the back, and I just woke up and I said,
• 2:06 - 2:08
"That can't be right."
• 2:08 - 2:12
I just had this visceral reaction that said, "I can see what the algorithm does,
• 2:12 - 2:16
"and I know it swaps everything, but it just seems too inefficient."
• 2:16 - 2:21
"It has this loop that keeps on going, and it's not a for loop, it's a while loop."
• 2:21 - 2:26
And it just seemed to me that it was possible that this loop could go forever.
• 2:26 - 2:28
Depending on the choice of random numbers,
• 2:28 - 2:30
this might never terminate, and that just seemed wrong.
• 2:30 - 2:32
It seemed like there was a much better way.
• 2:32 - 2:37
And in my head I came up with the shuffle algorithm that we showed before.
• 2:37 - 2:40
Knuth calls it Algorithm P for permutation.
• 2:40 - 2:42
It just seemed like that was the simple and correct way,
• 2:42 - 2:46
and this was just too complicated, and that really bothered me.
• 2:46 - 2:49
I thought that an algorithm should be guaranteed to terminate.
タイトル：
Bad Shuffle - Design of Computer Programs

more » « less
Video Language:
English
Team:
Udacity
プロジェクト：
CS212 - Design of Computer Programs
Duration:
02:50
 Udacity Robot edited 英語(米国) subtitles for Bad Shuffle - Design of Computer Programs Gundega edited 英語(米国) subtitles for Bad Shuffle - Design of Computer Programs Amara Bot added a translation

# English subtitles

## 改訂 Compare revisions

• API
Udacity Robot
• Gundega
• Amara Bot