Derangement

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.

Derangement

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 from which we
* @return a uniform random derangement
*/
export function derange<T>(array: T[]): T[] {

}

Solution

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

/**
* @param array the array from which we
* @return a uniform random derangement
*/
export function derange<T>(array: T[]): T[] {
array = array.slice();

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

return array;
}

Transcript

00:00 Today's coding interview question is called derangement.

00:02 And this comes from a request on a lesson on shuffling.

00:05 And as we will see, it is actually quite easy to end up

00:07 with derangement just

00:08 by a slightly poor implementation of shuffling.

00:11 Now, derangement does have real world applications,

00:13 for example, in peer reviewing assignments,

00:15 but we want to take each individual's assignment

00:17 and randomly assign it to someone else.

00:20 So this algorithm is useful to have in your toolbox.

00:23 So let's go. Now, we're going

00:26 to try something different for this particular lesson.

00:27 And I think the best way

00:28 to explain this particular algorithm is

00:30 to write the test first.

00:33 A arrangement is an arrangement of the original array such

00:35 that none of the items remain in their original place.

00:39 And that is exactly

00:40 what our test is ensuring within

00:42 an array of a hundred items.

00:44 We want to make sure that

00:45 after we invoke the range,

00:47 the item at an individual index is not equal to the item

00:50 that was present there before.

00:52 So with the test out of the way,

00:53 let's jump into our implementation

00:55 and build a skeleton

00:56 for the function that we are looking for.

00:58 We take an array of items T

01:00 and then return a uniform random derangement

01:02 of that input array.

01:04 Now to help us along in our journey,

01:05 we will bring in the random integer function,

01:07 which we have a lesson dedicated to so that we don't have

01:09 to recap that over here.

01:11 And then within the function body, the first thing

01:13 that we will do is we will create a copy of the input array

01:15 because we do not want

01:17 to be mutating someone else's own array.

01:19 And the way the algorithm is going to work is

01:21 that we will loop through the items in the array one by one.

01:25 And for each iteration we'll pick a random index from the

01:28 remaining number of items and put

01:31 that into the current position.

01:33 That is what this swap line is doing.

01:35 And then finally, we will return this arranged version.

01:38 Now, picking items from a random index,

01:41 excluding the current one, ensures that the item

01:43 that ends up at the current index is not going

01:46 to be the item that was there before.

01:51 And in terms of analysis, this is going

01:53 to be a uniform derangement where each item is going

01:56 to have the probability of one over N minus one

01:58 for ending up at the position where it does end up.

02:02 Now, even though we are carrying out the algorithm in place,

02:04 it might be helpful for you to visualize it as two arrays

02:07 and input array and an output

02:08 array where we are placing items.

02:10 And the probability of the first item

02:12 that ends up at position A is going

02:15 to be one over N minus one,

02:16 because we are going to pick it up from the remaining array.

02:18 And then for the second item, the probability will be

02:21 that it doesn't end up in the first place, which means

02:24 that it is unlucky.

02:25 That is N minus two divided by N minus one.

02:28 And then it does get picked up for the second iteration.

02:31 That is, it gets picked up with the probability

02:34 of one over and minus two.

02:36 And if you multiply these two, we end up

02:38 with the probability of the item in the second place

02:40 to be one over and minus one.

02:42 And then you can repeat this analysis

02:43 for the remaining items as well.

02:45 Very similar to how we did for shuffling.

02:50 In shuffling the probability

02:51 of each item at a particular place was one over N.

02:54 And over here it is one over N minus one.

02:57 So in a sense, shuffling is more random than the arrangement

03:00 because there are lesser positions for the item to end up

03:03 because we know that it's not going

03:05 to be in its original position.

03:06 And if you take a look back at this algorithm,

03:08 this is exactly the same as

03:10 what we implemented was shuffling except

03:11 for the one key difference

03:13 where we pick up a random item at I plus one to make sure

03:16 that the item that we get

03:17 for the current index is not the same as

03:19 what is sitting at the index right now.

03:22 One more thing to watch out for is that we have to make sure

03:24 that we terminate the loop when we only have one item

03:27 remaining, as there is going to be no item

03:29 to pick from the remaining array

03:31 to put into the current position.

03:35 And in terms of space

03:36 and time complexity, it is going to be constant space

03:38 as we are doing the swaps in place.

03:41 And in terms of time complexity, we are only looping

03:43 through the input array once, so it is going to be OFN.