Perfect Shuffle an Array

Pro Members Only

This lesson is available if you have an active subscription.

Alternatively, some member might be able to gift it to you.

If you already have a subscription, you can sign in.

Perfect Shuffle an Array

Subscription Required

You must have an active subscription to access this content.
If you already have a subscription, you can sign in.

Problem

/**
* @param array the array to shuffle
* @return shuffled version of the input array
*/
export function shuffle<T>(array: T[]): T[] {

}

Solution

import { randomInt } from '../random/random';

/**
* @param array the array to shuffle
* @return shuffled version of the input array
*/
export function shuffle<T>(array: T[]): T[] {
array = array.slice();

for (let i = 0; i < array.length - 1; i++) {
const randomIndex = randomInt(i, array.length - 1);
[array[i], array[randomIndex]] = [array[randomIndex], array[i]];
}

return array;
}

Transcript

00:00 Now there are a lot of algorithmic questions

00:02 that are related to randomization,

00:05 but the most popular one that I can think of is the problem

00:07 of shuffling, for example, shuffling a deck of cards.

00:10 And that is the problem that we will look at in this lesson.

00:14 So let's go. Now

00:16 before we look at anything else, the first thing

00:18 that we need to clarify is the concept

00:20 of the perfect shuffle.

00:22 What a perfect shuffle essentially means is

00:24 that any item can appear in any position

00:27 with equal probability.

00:29 So if we have N items in end positions,

00:31 then any item can appear in any position

00:34 with the probability one over end.

00:36 Now, that might sound like a hard ask,

00:38 but it's actually quite easy to achieve.

00:41 Fundamentally, we pick an item one by one

00:43 and put it in the output.

00:45 So assuming we have an array, A, B, C, D, F, whatever,

00:49 we pick an item at random.

00:50 Let's say we pick C and we put it in position zero

00:53 and we pick a next random item.

00:55 Let's say we pick D, put it in position one,

00:58 and then pick the next random item and so on.

01:01 And we can actually prove the mathematical correctness

01:03 of this algorithm quite easily.

01:05 So let's do that next.

01:07 Now, since we're going to pick the first item at random,

01:09 the odds of it getting picked are going to be quite fair.

01:12 It's going to be simply one over N.

01:13 As we have N items,

01:15 things get a bit more interesting when we pick up the next

01:18 item at index one.

01:19 The odds of it getting picked are essentially the odds

01:22 of it not getting selected in the first attempt

01:24 and getting selected in the second attempt.

01:27 Now, the odd of it not getting selected in the first attempt

01:29 are actually quite high as we have N minus one items

01:32 that will not get picked among the N items.

01:35 The odds of it getting picked in the second attempt is

01:38 simply going to be one over the N minus one.

01:40 Items that we will be picking amongst

01:42 the N minus ones will cancel out with each other, leaving us

01:46 with the standardized one over N.

01:48 And this process will continue

01:50 for all other attempts as well.

01:51 Only the chain of the item not getting in into nth

01:54 attempts will get longer.

01:55 However, we will always be left

01:57 with one on top and N at the bottom.

02:00 So with the mathematical analysis

02:02 of picking an item randomly one by one out of the way,

02:05 let's look at our example once more.

02:07 Our objective is to randomly select the items one by one.

02:10 However, there is one more complication that we need

02:13 to think of at each step.

02:15 We have to remember which items we have already picked

02:18 and which items are still available to be randomly chosen.

02:21 Now, we could do this in separate data structures,

02:24 however, it's actually quite easy to do in a single array.

02:27 So let's look at an example.

02:29 We will essentially have the array as a shuffle

02:31 and an un shuffle portion.

02:33 We start off with a completely empty shuffled portion.

02:37 So in our first attempt, let's say we pick C,

02:40 move it into index zero,

02:42 and we take whatever was there, for example,

02:44 in this case it is A,

02:45 and move it into where C originally was.

02:48 Now we have this shuffle portion containing C

02:50 and this uns shuffle portion

02:52 containing all the other members.

02:54 And the next item we pick,

02:55 we will pick randomly starting at index one all the way

02:58 Till N.

03:00 Let's say we pick T, we swap what was already there,

03:03 which is the character B, and move it into where D was.

03:06 So in each step, the shuffle portion gets bigger

03:08 and bigger till we eventually run out

03:10 of all the uns shuffled members.

03:12 And then we have a completely shuffled array.

03:15 Now understanding how the algorithm works might have been a

03:18 bit involved, but quoting it up is

03:20 actually going to be quite easy.

03:21 We start off by bringing in our random integer function,

03:24 which we coded up in our previous lesson.

03:26 And then we have this template function,

03:29 which will take an array of type T

03:30 and return an array of type T.

03:32 And the first thing that we will do is

03:34 that we will create a copy of the input array

03:36 as I don't like mutating our input arrays.

03:39 However, if you'd lead this call

03:40 to slice this algorithm will still work perfectly fine.

03:43 It's just that the input array is

03:44 what we will be shuffling in place.

03:47 Now for the main core of the algorithm, we simply have

03:49 to loop through end times for an items.

03:52 And in each iteration, the first thing

03:54 that we do is we get a random index starting at I all the

03:58 way till the end of the array,

03:59 and then we swap the item at the random index

04:01 with the item at the I index.

04:04 This means that the array has been shuffled up till I,

04:07 and then the loop continues with i plus plus.

04:10 This one line swapping of I item

04:13 with the random index item is a JavaScript trick

04:15 that I have a lesson dedicated to

04:17 as well, if you are interested.

04:19 Now, once this loop terminates,

04:20 we've essentially placed N items into N positions,

04:23 which is exactly what we want our shuffle algorithm to do.

04:26 Now because we are only looping

04:28 to the input array once the time complexity

04:30 of this algorithm is OFN.

04:33 And because we are creating a new array with array

04:35 to slice the space, complexity is OFN.

04:39 However, if you remove this call to slice,

04:41 we can essentially shuffle the input array in place,

04:43 therefore giving us a space complexity

04:45 of OF one, which is constant.

04:49 Now shuffling is a very well understood problem,

04:51 and the algorithm that we implemented in this lesson is

04:54 known as the modernized version of the Fisher Yates Shuffle.