Материал готовится,

пожалуйста, возвращайтесь позднее

пожалуйста, возвращайтесь позднее

Next we're going to look at an easy

application of sorting to related problem

called Shuffling. So, suppose you have a

deck of cards. One of the things that you

might want to try to do is to simply

rearrange those cards into random order,

that's called shuffling. Here's a way to

get shuffling done using a sort and seems

like the opposite. The idea is, just

generate a random real number for every

array entry and then sort using those

random numbers as the keys. That's an

effective way to get things shuffled. And

it's possible to prove that, that produces

a uniformly random permutation of the

input if there's no duplicate values,

assuming that you have a real numbers that

are generated uniformly at random. And

that's just means that it's well shuffled

that every possible way of shuffling the

deck appears with the equal probability.

That's fine but it requires a sort and a

sort seems like a lot of work for this

problem and the question is, can we do

better? Can we have a faster way to

shuffle? Do we really need to pay the cost

of a full sort? The answer to that

question is, no. There's actually a very

easy way to rearrange an array so that

the result is a uniformly random

permutation. It only require a linear time

to get the job done. Let's look at the

demo. The idea this to pass through the

array from left to right with an index i

as we've been doing but now we start with

the array in order. And actually, it

doesn't matter how we start the array and

every time we pick an integer between

0 and i uniformly at random and, and

swap a[i] with that integer. So, let's

look at the beginning, we don't do

anything just swap it with itself. Now,

with i = 2 or i pointing to the second

card we generate a random integer in

between 0 and i, in this case it's the

one to the left and we swap those.

Increment i, generate a random integer,

this time it's going to be the first one

again, swap them. Increment i, generate a

random integer, swap them. Increment i,

generate a random integer, swap them. And

continue in that way. Swap. So for every

i, we do exactly one swap. Now, card could

be involved in more than one swap but

that's not an issue. The point is that the

cards to the left of i are shuffled there

uniform, randomly shuffled. On this case,

i and r are the same. There's no swap.

Increment i, generate a random r, swap them.

And at the end we have the deck shuffled.

That's a linear time shuffling algorithm

making use of randomness. It was proved

through actually a long time ago even

before computer implementations that if

you do that, you get a uniformly random

permutation and it only takes linear time.

So, that's definitely a way to get a deck

shuffled quite easily. Easy to implement.

Now it's key that the uniform random

number will be between 0 and i-1. You'll

often see programmers thinking that

they're implementing a shuffle and they

just choose for every entry, they just

choose random place in the array to

exchange it with and that doesn't really

work. You could do the items between i and

n-1, the ones that you haven't seen

yet and that would also work but doing a

whole array doesn't give you a uniformly

random result. So, with that one caveat,

this code is almost trivial. And it's a

method in our standard random class. Now

if you're going to be using random methods

that depend on randomness in real

applications, you do have to be careful.

application of sorting to related problem

called Shuffling. So, suppose you have a

deck of cards. One of the things that you

might want to try to do is to simply

rearrange those cards into random order,

that's called shuffling. Here's a way to

get shuffling done using a sort and seems

like the opposite. The idea is, just

generate a random real number for every

array entry and then sort using those

random numbers as the keys. That's an

effective way to get things shuffled. And

it's possible to prove that, that produces

a uniformly random permutation of the

input if there's no duplicate values,

assuming that you have a real numbers that

are generated uniformly at random. And

that's just means that it's well shuffled

that every possible way of shuffling the

deck appears with the equal probability.

That's fine but it requires a sort and a

sort seems like a lot of work for this

problem and the question is, can we do

better? Can we have a faster way to

shuffle? Do we really need to pay the cost

of a full sort? The answer to that

question is, no. There's actually a very

easy way to rearrange an array so that

the result is a uniformly random

permutation. It only require a linear time

to get the job done. Let's look at the

demo. The idea this to pass through the

array from left to right with an index i

as we've been doing but now we start with

the array in order. And actually, it

doesn't matter how we start the array and

every time we pick an integer between

0 and i uniformly at random and, and

swap a[i] with that integer. So, let's

look at the beginning, we don't do

anything just swap it with itself. Now,

with i = 2 or i pointing to the second

card we generate a random integer in

between 0 and i, in this case it's the

one to the left and we swap those.

Increment i, generate a random integer,

this time it's going to be the first one

again, swap them. Increment i, generate a

random integer, swap them. Increment i,

generate a random integer, swap them. And

continue in that way. Swap. So for every

i, we do exactly one swap. Now, card could

be involved in more than one swap but

that's not an issue. The point is that the

cards to the left of i are shuffled there

uniform, randomly shuffled. On this case,

i and r are the same. There's no swap.

Increment i, generate a random r, swap them.

And at the end we have the deck shuffled.

That's a linear time shuffling algorithm

making use of randomness. It was proved

through actually a long time ago even

before computer implementations that if

you do that, you get a uniformly random

permutation and it only takes linear time.

So, that's definitely a way to get a deck

shuffled quite easily. Easy to implement.

Now it's key that the uniform random

number will be between 0 and i-1. You'll

often see programmers thinking that

they're implementing a shuffle and they

just choose for every entry, they just

choose random place in the array to

exchange it with and that doesn't really

work. You could do the items between i and

n-1, the ones that you haven't seen

yet and that would also work but doing a

whole array doesn't give you a uniformly

random result. So, with that one caveat,

this code is almost trivial. And it's a

method in our standard random class. Now

if you're going to be using random methods

that depend on randomness in real

applications, you do have to be careful.

Загрузка...

Выбрать следующее задание

Ты добавил

Выбрать следующее задание

Ты добавил