Coding Interview Problem: Permutation Generator

Coding Interview Problem: Permutation Generator



Views:84900|Rating:4.29|View Time:18:31Minutes|Likes:636|Dislikes:106
Follow along as we dive into the problem of creating a permutation generator using C++. We’ll walk through an efficient, in-place solution that leverages lexicographic ordering and incrementation. A full text version of the code is available here:

welcome back for episode 4 the unqualified engineer my name is Jackson Gabbard and I'm going to sure put you through another coding interview problem this time around so today's problems called permutation generator and the premise of this problem is that you're going to write a function that will return the generator and if you're a Python coder a generator will be a very familiar concept people who write in other languages this is not so familiar if you look at JavaScript coder this is a bit like currying or like sort of private state from a function that you can call over and over again that will each time return a different value some generators are infinite you can just keep calling them forever but in this case our generator has a very specific number of returns it can pull a return in factorial values and the reason it's in factorial is because that's the math behind permutations now I know what you're thinking who the is ever going to use this for anything I can't really argue with you there I also feel like who the is ever going to use this for anything I I can say that I talked to one of my friends who's a very strong coder and also a big fan of coding competitions like the ACM were top coder and he was very excited about this problem specifically because he is had to do this many times he was able to recite the algorithm from memory so for what it's worth there are competent coders who think of this as a useful and interesting problem here's the setup the challenge is to create a generator function that will take an integer N and this generator when called will return a new permutation of the numbers between 1 and n until all of the permutations have been exhausted so for instance if the input was 4 if the integer n was 4 then our generator would start by returning 1 2 3 4 then the next call it would be 1 2 4 3 and then 1 3 2 4 and so on until we've exhausted all of the possible permutations and today we're going to code in C++ that's right everyone's favorite weird language now it's worth pointing out that I'm not actually a real C++ coder you know what they say you can teach an old dog new tricks they say what do you say you can't teach a JavaScript er to write code no is it anyway I've been learning C++ and I'm really excited to attempt this video in C++ generally I would say don't ever code in a coding interview in a language that you don't know exceptionally well but in this case I had time to research and make sure the code is correct and have it reviewed by some of my competent C++ coder friends and so I feel confident that I'm putting forth code here that would not get you fired or lose you a job if you were to emulate it and because it's C++ I'm happy to say we're going to code with Hungarian notation today just kidding we don't hate ourselves now let's talk about this problem in concrete terms we've already talked about the Beckman we start with something like one two three four you could generate these permutations in any order there's no requirement of this problem to keep it in one order or another now if you take the problem the way it's drawn out here you might immediately notice that these numbers are basically in numerical order but given that they're not actually integers on their own there are sets of integers maybe I should have put commas between so with the commas included it's actually a little bit clear that they're not so much in numerical order as they are in lexicographic order and if you think about it this way it could actually be anything that can be ordered in a deterministic way instead of numbers it's like we're using numbers here but it could be anything these could be letters from the alphabet they could be your friends and the order in which you like them they could be political parties sort of by average IQ and so really the problem here becomes not so much generating permutations but actually figuring out how to increment a vector of objects lexicographically because if you enumerate all of the possible lexicographic ordering of the vector you will therefore also enumerate all of the possible permutations because they are one in the same let's look at a more complex example take for instance a permutation of the integers between 1 & 5 how about 3 5 4 2 1 now if you stare at this long enough you would eventually arrive assuming you follow an algorithm like design here you would arrive at the notion that it is for one two three five then the important question here is why or rather how it's easy enough for anyone who's ever going to count to say why because when you count up past this the next number you can find that as all the digits in it is four one two three five but we're not just doing counting here we're actually implementing lexicographic incrementation but i think about these kinds of problems or any type of puzzling question which i absolutely consider this to be which is part of why i think is a shitty question to ask in an interview the thing I look for is what I would call like a grip a piece of puzzle a detail of the problem that lets you sort of claw your way crawl through the muck and mire of the problem until you understand how to actually solve and in this case one of those grips is that the number is in reverse sorted order up until there is a decrement up until the numbers go down so if you start the right side you'll notice it's 1 followed by 2 which is bigger followed by 4 which is bigger followed by 5 which is bigger and then a 3 that's a super super key piece of this problem because no matter which version of this problem you're trying to solve anytime you go down that's where the incrementation happens that's the place in the vector where the opportunity to increment comes from and you can know this because you'll notice before that number all of those numbers are the biggest possible numbers they can have you're putting the biggest numbers in the highest order places in the vector which means you can't possibly increment from there so you have to have a place where it descends in order to be able to increment so if we assume at that decrement at that point where the numbers go down but that's where we're going to start our process of creating the next permutation or the next lexicographic incrementation then the question becomes okay so what do i do like what actually happens here and if you look at the after case if you look at the place that we're going to get to one thing you should notice is that there has been a reversal specifically it's all the numbers after the place that we care about they're all now in sort of us in water another way to say that is to say that the biggest numbers are in the lowest order positions in the vector knowing these things we've got major parts of the problem Within Reach one we need to find the place in the vector where the value goes down where we go from a higher value to a lower value and we need to reverse sort the rest of the vector after that point but we're clearly missing a detail here because if we just apply that we've talked about what we would end up with would be 3 1 2 4 5 and that's obviously now that we have in second case we have 4 1 2 3 5 but those two numbers are only off from each other by one digit there's one misplaced digit in the 3 1 2 4 5 case from the 4 1 2 3 5 case and that is that the 3 in the 4 are misplaced and that's the third grip of this problem that's the third trick thing to notice that in order to implement lexicographic incrementation when you find the decrease the next thing you have to find is what's the next biggest number that should go in that spot so you find that number which in this case is 4 then you swap those numbers you replace the 4 with the 3 and the 3 to the 4 so then what you have would be 4 5 3 2 1 and you'll notice at that point that you've got a 4 and then you've got a reverse sorted suffix you could comment and you've got a reverse sort of tail and so from there it's really easy to just swap the start of the table at the end of the tail and the next one after that with the next-to-last and the next one after that the next one however many you have to reverse the tail of the list and what you end up with is exactly what we want here the exciting part is this works for every case it works whether the decrease is at the very end or at the very beginning or if there are many decreases in the same vector you start at the rightmost one and that will make sure you're always modifying your lowest order positions of the vector first and then you get to the higher order ones later and that's how lexicographic implementation works ok ok ok enough with this understanding the problem nonsense let's get the writing odhh so we're going to code and C++ and we said that we're going to do this as a generator now I'm basically an expert in C++ and when I think of something you can call over and over again and you can get a different value I think of funk tours now I have very limited whiteboard space here so I'm going to break this problem into two parts one part is going to be setting up the structure of the funk tour and the second part is going to be implementing the logic to generate the permutations so let's talk about the funk tour first but I can already tell I'm going to get grief from some snobby C++ programmer which as I'm wasting my time with things like vowels and upper case to your friend who wants this to be permutation underscore juror you I bet your favorite variable name is a and I bet everyone hates reading your code so I'm going to call my abstraction permutation generator so what's this thing going to do well we know it's going to take an end when you take some size and it's going to create a vector of all of the numbers between 1 and that number so let's give ourselves an affordance for those things C++ functors effectively have a constructor that stores some initial state you may implement the function execution operator to do something with that state there is not an algorithmic programming especially of course there are a million different ways to construct objects in C++ I'm going to leave it at this for now choose your own adventure in your own code so the only thing we need from here is the function execution operator to be implemented in our case it's going to return a vector of integers so that is the very healthy skeleton of the code and what this will allow us to do is to create a permutation generator and then call it whatever we need you so now let's zoom in on this function execution operator ok so imagine we're inside the class we're inside a permutation generator and we're implementing the contents of the operator for function execution now if you recall we didn't actually fill in our vector it's empty right now so the first thing we should probably be doing here is when someone execute the function we should fill that sucker with contents now this is debatable right like some people would say oh you should do that the constructor I kind of agree but what if you're instigating millions of these for instance and you're not going to execute all of them maybe you can't know which ones you're going to execute in that case it makes sense to delay filling the Becker because you don't even know if you're going to need to use that memory also this gives us an easy way to start the algorithm off if we start by incrementing then we're going to skip the first case entirely so controversially I'm going to fill the array inside the function execution operator you can send hate mail to JG @j GGG so fill I'm assuming to be some sort of useful fast way to fill the vector which would probably look something like this now the next thing we want to do is find the place where the value decreases and assuming we're not at the very end of the permutation we will always find a value the decreases in fact if we don't find a value the decreases we can be very sure that we have finished all of the possible permutations the easiest way to find a decrease is to go to the very end the very right side of the vector and compare the last two now you can have a decrease of just one number the FFT takes two numbers to have a decrease so what we want to do here then is start with the next-to-last item and compare it to the last item that will be our way of comparing the last two so we're just going to use a loop here to walk from the right side to the left side comparing the number we're at to the number that came to the right of us and see if we're smaller than the number to the right of us if we are then we have found the special case now you'll notice we're avoiding the off by 1 here because we started at -2 we started at the next-to-last and so it's always safe to go 1 more than us because we skip that one initially but the next thing we have to be worried about is what if we run off the front of the list in C++ if you run past the beginning of a vector you are in an undefined state it's no man's land there Dragons be honest groups group with a ruler you don't want to go there but we do want to go all the way to the very beginning because if we're at the first number and we haven't decreased yet then that means that the biggest number is in the first position and we're done we can't possibly create another permutation so we do need to say while decrease is greater than or equal to the very first position in the vectors so we have to do in the loop is decrement our decrease iterator but there's a special case here and that special case is if we are right at the beginning of the vector if we're there we're done we cannot possibly create another permutation so one thing we could do here is we can throw let's let's keep it real simple for the whiteboard and say let's just return an empty vector so if we're here we can assume that decrease is at the point in the vector where the number has gone down so if we think back to our example case of 3 5 4 2 1 we can be sure that decrease is at 3 now who remember back in the algorithm what we need to find is the next bigger number in the tail in the sort of end piece here and in the example case we're talking about here that's 4 but we don't know what it's going to be in every single case what we do know is it's going to be the first greater number in the tail piece from the decreased number that you've already found so in this case it's 4 but it could just as easily have been that 4 was on the left side of the decrease point and in that case the next biggest number would be 5 so let's find it so we'll start at the very right edge of the vector and we'll come the left words if you remember the numbers in the tail are going to be in descending sorted order so if we're come from the right side as soon as we find a number that's bigger that's our winner because any number that's to the left of that number is going to be bigger than that number which would mean that we would skip numbers in generating the next increment once we finish this loop we know that larger refers the first bigger number in the tail then the decrease number and if we think back to the algorithm as we discuss it earlier the very next thing we need to do here is swap these two values now I'm going to omit the details of swap but let's assume it looks something like this we've almost finished the algorithm as we described it initially step one was to find the decrease in the vector step two was to find the next bigger value in the right side of the vector from that decrease step three was to swap them step four is now to reverse the remainder of the vector so that it will go from descending sorted order to ascending sorted order putting the highest order numbers at the lowest order positions so let's do that I think we can easily do that with just two iterators and a loop so just to check our indexes there we've got beta n minus 1 which in this case will point to 1 then we've got decrease which was 3 but is now 4 and we're going to move one to the right of that which should point us at 5 and so the part we're going to be swapping is 5 3 2 1 and 4 will be the beginning of the list so now it's another simple loop to reverse the remainder of the list so we start from the left and we start from the right we swap the value at each position with the value of the other position and then we move both pointers inwards towards each other and I believe with this we're done we have modified our list in place and now we can just return so so while generating all the possible permutations of a list of numbers is actually an N factorial complexity problem here our algorithm is only doing one iteration across the list for every call so it's an O of n complexity solution to generating the next possible permutation so I guess you could say this is an N factorial times in problem if you wanted to include the complexity of generating all of the permutations which of course in Big O would just be in factorial probably the most exciting thing about this though is that it's an in-place manipulation so there's no additional memory this is a bit higher complexity than some of the other problems with base and like I said before I really think of this as kind of a well to put it in my terms I would call this a dickhead coding interview question not because it's super high complexity the complexity is tractable because there are too many little things that you have to notice in order to solve it efficiently this falls into that category of question that you either get or you don't get and it has nothing to do with your ability to code a solution to it effectively and to me that makes very bad interview question the best to give you questions are ones where you have something to figure out it's not so puzzling that you don't happen to get the moment like your screw to the rest of the interview I'm including it in my video series because it's absolutely the kind of question that you would face off against at a very sort of algorithmic kind of company the kind of company that really prides itself on its computer science ii prowess and that's all i hope you guys enjoyed it if you have comments if you think my c++ sucks if there's a million different ways to do it please comment below i would love to see a nerdy smart comment fight on youtube for once so go for it

39 Replies to “Coding Interview Problem: Permutation Generator”

  1. Marco Suma

    Very smart approach. I would have proposed recursion but this is brilliant!

    Two things I believe they are wrong..
    First thing is that “fill” function should fill it in descending order and iirc you do it in ascending order.
    Second thing is that the stop condition (i.e. the current base is fully ordered in ascending way..) should be checked outside the while.

    Am I correct ?

  2. John Madsen

    Permutations or combinations are also used for brute force password cracking. Also, simple first, middle, last name generation.

    Simple to do. Now try to optimize synchronize it across threads.

    Also it is very impolite to wear just underwear on camera. Unless it’s in the ghetto film. T-shirts are not cool.

  3. Daemon Electricity

    I seriously got this fucking problem on a code test for a full stack web developer. You don't ask the guy who builds houses to actually be a materials scientist. He just needs to know how to build a house. A web developer knows how to implement APIs, fairly advanced understanding of networking in a practical sense, databases, sockets, deployments, to some extent, browser behavior, best practices for common problems implementing web specific stuff. You hire actual mathematician and algorithm specialists for this kind of shit and ask them these kinds of questions. Even the Fibonacci is pushing the boundaries of reasonable coding tests for web developers.

    You can joke that their not coding, and whatever, fair enough, but they are building shit with a set of skills that doesn't necessarily overlap with what you're actually calling a coder. I think all of this is nested in the autistic need for people who live eat sleep and breathe algorithms and memorize whatever flavor of the month datasheet are real coders.

  4. Sravan Vedala

    How can anyone on earth could be more boring than this guy. I am relatively very patient as I earn all my stuff from youtube, but Oh boy, this video literally tested my patience…

  5. Keesha Readus

    Lmfao!!! He said "Fuck you! I bet your favorite variable name is a and everyone hates reading your code" I just cried laughing lol.

  6. jasdeep singh Grover

    there can be another way… if we have 12345… swap the last two terms 12354 .. swap them again and treating the last two as one term swap it with third last term… 12453 swap 45 again… 12543… now treat the last three terms as a single term and continue with the fourth last term… and so on… I am not sure but I guess we can do that with recursion

  7. 796f7574756265

    I must finally get the little whiteboard for myself to practice. Seems that nowadays you can't escape those interviews.
    Great channel, big thanks for your time!

  8. Andrew Farley

    Great vid man! I really enjoy the energy, humor, and enthusiasm you bring. Most people coding on YouTube just drawl on monotonously and don't give good explanations. Keep it up!

  9. TarriestPython

    Does this algorithm assume that the list starts ordered from smallest to largest, as the "value" of the whole "number" gets larger each time? Therefore if it wasn't sorted at the beginning then the number of permutation would be less than the actual number of permutations?

  10. prashanth-g

    +Jackson Gabbard I have seen a practical use of permutations in a police investigation where the police officer uses a string as a clue and found list of permutations and found the exact word which they need.

    Anyway this video is awesome.

Leave a Reply

Your email address will not be published. Required fields are marked *