Hello and welcome. I'm James Murphy and this is mCoding. Today, we're learning about the crazy code behind Python's itertools permutations function. What permutations does is pretty straightforward. It gives you all of the permutations of an object. The second parameter allows you to get partial permutations, or sequences from the original set taken without replacement. Using it is straightforward. Just give it the items that you want permutations of and the length of the partial permutations that you want. Looping over the results, we see that this is a pretty easy way to get all the permutations. But have you ever thought about how you might implement a function like this? Well, a viewer of mine, Jerry, was thinking about this. Jerry sent in the following code that he found in the Python docs. Technically, you're probably using CPython. And in CPython, this function is actually written in C. But it still does essentially the same thing. So, this is just the Python version explaining how it works. But wow. This code looks like an absolute mess. What's going on here? We've got conditional breaking, mutating objects as we're looping and branching inside of a for-loop inside of a while-loop. Not to mention, we're also using the somewhat obscure in Python for-else paradigm. If I saw this in a real codebase, I'd half expect it to have a comment saying: BLACK MAGIC, DO NOT EDIT. This is the kind of code that looks so complicated that it scares people away from understanding it. And before my viewer wrote in, that's exactly what happened to me. I've seen the documentation for itertools before. I've read this code before. But after one glance, I decided that it was probably some clever mathematician that came up with the algorithm. And there's a 20 page proof attached to it explaining why it does the right thing. But I claim that the underlying idea is actually very simple. And by the end of this video, you too are going to understand it. Surprisingly enough, the key to understanding this code is to not try to understand the code. What I mean is, don't try to figure out what all these things are doing. Instead, try to just solve the problem. If you had to come up with a way to iterate over all the permutations of some list, how would you do it? I asked this because the itertools code is using probably the simplest algorithm that you could come up with. Optimized into oblivion. And by starting with the simple algorithm, you too can get to this one. So, let's start from the ground up. The simplest version of this problem is to just count how many permutations are there. Pick the first element of your permutation. That's n choices. For the second element, you've got n - 1 choices And so on until you get to the r-th element. Then we just multiply the numbers together. So, we start with n * (n - 1) * all the way down to (n - r + 1). If r was equal to n, which is the case of full permutations, then this gives n factorial. But just for example, suppose we have 5 things and we want 3 permutations, then we have 5 choices for the first thing, 4 choices for the second thing and 3 choices for the third thing. This is a very straightforward counting argument. You can implement this using reduce. Or just using a for-loop, you can multiply the things together. The next step is to take our counting procedure and turn that into a recursive algorithm. Well, we started counting by picking an element. Okay. So, suppose that we pick the first element. Well, if we want to find a permutation of length r and we've fixed the first element being 0, in this case, then what's left to do to find all the permutations that start with 0 is to just find all the permutations of length r - 1 from the remaining items. But that's exactly the same question just on a smaller input. We can just keep track of what part of our permutation is fixed and what part remains to be enumerated. Each time we recurse we fix another element. And eventually, we fixed our elements which is the length of the permutation that we're looking for. Let's take a stab at implementing this recursive structure. Like many recursive problems, the actual recursion will be implemented inside some helper function that has some additional information that we don't want to expose to the user. In this case, the additional information is this variable i which tells us the number of things in the permutation that have already been fixed. At this point, don't worry about input validation or anything like that. And just assume that items is a list from 0 to n - 1. Remember, our function is a generator. It runs and then it pauses and can yield a value. Each time we have a new permutation, we'll yield. Then the caller can just look at the current state of the items to determine the permutation. This is just an implementation detail and we can hide that from the user by doing something like this. Every time our recursive generator yields, we just make a copy of the first r items and that's our permutation. First up, our base case. r is the number of remaining things left to choose. If there are no more things left to choose, then we're done. Yield the current permutation and stop. If you're not sure why the yield should be there, then consider the case where someone asks for length 0 sequences. How many zero length permutations of n items are there? Well, just one. The empty permutation. Then the recursive part of the algorithm looks like this. We want to say for each of the remaining items, fix that item and then recurse. So, if the fixed portion of our permutation is just 0 so far, then we want to fix 1 and recurse and then fix 2 and recurse and then fix 3 in recurse and so on. The location just after the bar that determines the things that haven't yet been fixed is exactly what our local variable i represents. So, this loop should be a loop from i to the end. In order to fix an item, we just move it into the i-th position. The way we do that is just by swapping the i and j entries in the list. Notice what happens when we swap i and j entries repeatedly. From here to here, we swap 0 and 1. Then we swap 0 and 2 to get to here. Then 0 and 3 to get to here. Notice that each iteration puts the element that was moved in the previous iteration back in its original location except off by one. So, after iteration 0, the 0 moved to 1. After iteration 1, the 1 moved to 2. After iteration 2, the 2 moved to 3. After the last iteration, we just have n - 1 in the fixed slot And then all the numbers in their original order just shifted over by 1. This is actually a slight problem. After swapping an item into the correct place, we would like to just make the recursive call. The recursive call is pretty straightforward. We just say one more thing is fixed and one less thing needs to be fixed. But remember, I'm not making copies here. So, the recursive call might modify items. If items is getting scrambled, then how do I know that I'm choosing each element one time? Say, I swapped 0 and 2 and then made a recursive call. If all the numbers got jumbled then when I go to swap 0 and 3, the 3 might not be in that position anymore. Well, the great thing about recursion is that you can assume that a recursive call has some nice property And then use that property as long as you're willing to maintain that property in the current call. So, what I can do is add the restriction that after I yield all of the items from the recursive call, the items are going to be put back in the exact same position that they were in before the call. If I have 0, 1, 2, 3 and so on in order, I can swap in the next position, make a recursive call, iterate over all the results. And after the iteration is done, I'm in the same order. So, from the view of the caller, at this point in the code, items has the exact same state as it did right before the for-loop. That's very convenient for me. But now I have to maintain that property. After I swap 0 1, 0 2, 0 3 and so on, we end up in this state. We have the last element at the position just before the bar followed by the rest of them in order. In order to maintain the invariant and get back the original order, I just have to take the item just before the bar and push it to the end. Everything else slides left one and we're back exactly where we started. That means, here after the loop, we need to push the i-th element to the back of the list. My preferred way to do that is to just pop the i-th element and append it. Let's quickly fix this error. That's supposed to be the first r items not the last r items. And then we should be good to go. And there you have it, printing out the 3 permutations of 5 elements. You can compare against the itertools output. They're the same. So, let's get rid of these unnecessary comments and just take a look. Now, I get it. if you're not that familiar with recursion, then this could still be a bit tricky to understand. But if you know the basics of recursion, this is one of the simpler recursive algorithms. It's a pretty straightforward. Just do a base case, loop over some remaining choices and then do the recursive problem and then restore an invariant. If you're familiar with recursion, this really is one of the first algorithms that you'd come up with to solve this problem. And in my opinion, it's actually quite readable for what it does. It reads like the counting argument. Try all the choices, fix that choice and then find the smaller permutations. If this was the algorithm in the itertools docs, I don't think that anyone would have emailed me about it. So, why doesn't itertools use this approach? What if I want just the first few permutations of a really long list. Say, I take 0 to 1999. There are 2000 factorial permutations which is way too many to fit in memory. But itertools has no problem listing off the first hundred of them. Let's see what goes wrong with our version. In our version, we get a recursion error. And this makes complete sense. What's the depth of our recursive call stack? We decrease r by 1 with every recursive call. So, we make approximately r recursive calls. We can find out how many function calls we can have on the stack by printing out the recursion limit. Technically, all functions count towards this, not just recursive calls. So, it should be called something like 'get function stack limit'. But we're just being approximate anyway. For me, the recursion limit is a very small 1000. You can change the recursion limit with this call. But in this case, that still doesn't work. It ran for a while and then crashed because Python's stack isn't big enough. Yeah, you can increase the stack size a little bit. But this still is just not the right approach. If we want to support really large values of r, then we have no choice. Recursion is out of the question. So, how do you take a recursive algorithm and change it into a not recursive algorithm, an iterative algorithm? Well, keep in mind at the level of your hardware, there is no such thing as recursion. Everything at the level of machine code is iterative. So, there's some kind of automatic process that's happening that's getting rid of the recursion. You're running some code. When you make a recursive call, you put another function call onto the function stack. The function stack is a data structure that your computer is maintaining for you. So, the general purpose way to get around this problem is to use your own stack. Function stack space is very limited. But if you make your own stack, you can make it as big as you want, up to your computer's memory limit. But this video is already too long. So, we're not going to take that approach. Instead, we're going to take the much less general approach of trying to be clever. And yes, person-already-typing-in-the-comments, I too agree that you shouldn't try to be clever. But I guarantee you, this code was created by someone being clever. Here's how we'd be clever with the recursive function. The goal is to eliminate all the recursive calls. The only outside observable property of this function is that it yields at the right times and then it swaps the elements in the right order. If I swap 0 and 1 and then yield and then swap 0 and 2 and then yield, it doesn't matter whether that happened because of a recursive call or if I just did those things in that order. Let's just take a look. What's the order that these swaps are happening in and that these pushes to the back are happening in? Each time a swap occurs or a push to the back occurs, I'll just print out a message. Here are the swaps and shifts for n equals 5 and r equals 3. I also print out a little diagram of where i and j are when they're swapping. This way we can visually see which locations are swapping and in what order. If you count them, there are five level zero operations. Each one surrounded by four level 1 operations. Each one surrounded by three level 2 operations. Which brings us back to our original counting argument. Our innermost recursive call is looping over the three possibilities for this last slot. The next recursive call up is looping over the 4 possibilities for that slot. And the outermost call is looping over the 5 possibilities for the first choice. So, what's happening is a kind of weird countdown timer. Each column starts with the number of possibilities from the counting argument. So, here we're using 5 4 3. Then you start from the right and count down 3 2 1 0. When you hit a 0, that means you've tried all the possibilities for the previous column and need to switch to the next choice. Well, that means there's one less choice for the previous column and three more for the next column. And then you repeat. Eventually, you get to 5 1 3 2 1 0 At which point, we've used up all the possibilities for that column. So, we take the next possibility from the outermost column. And then the whole thing starts over on the inner ones. We keep going until we're out of choices for the first column and that's where we stop. We could completely get rid of our recursive calls if we could just iterate over numbers in this way. Okay, that's a much easier task to set our sites on. I envision this countdown as kind of like a weird clock mechanism. So, I'm going to call these things ticks. This is what stores the number of remaining possibilities for each of the items. We'll start with the while loop to just keep ticking the clock. And then in the loop, when we discover that there are no more possibilities, we'll return. We want to take down numbers starting from the right. So, we're going to loop over this reversed range. Every tick, we subtract 1 and then yield our current state. The current state is going to be a tuple of the index that just changed and the current ticks. If this were a general purpose function in the library, I would probably make a copy of the ticks here. But because its only purpose is to be used in our permutations algorithm, we don't need to make a copy here. We'll just keep in mind that we keep getting back the same copy of ticks mutated. After we do a tick, we need to check if we need to do a carry. We do a carry if at the current position we hit 0. Then we can calculate the number to reset it to based off of its distance from the start. When we do a carry, we reset the number back to its original value. Then since we did a carry on the next iteration, we need to subtract from one index to the left. Well, we're looping from right to left. So, that's what happens automatically. So, what we actually need to do is not do that if there wasn't a carry. In other words, if there wasn't a carry, then break so that the while will start again. And we'll start from the right. Then we need to terminate the while-loop somehow. We want to stop when there are no more possibilities for the very first location. So, when this number hits 0. There are a few ways to accomplish this. The most obvious way is when there's a carry, just check if you're at index 0. And if you are, then it's over. Another way to do this is with a for-else. If you've never seen for-else before, what it does is it executes the else clause if the for loop terminates normally. So, if it gets to the end of the range or the range was empty, then it will execute this statement. If there's a break or an exception thrown, then it won't execute the statement. In our case, a normal end of the for-loop means, we tried to carry past 0. And so, we should stop there. Now, using the iterative countdown function, we can write our iterative permutation function. We start off with a yield for the identity permutation. Then we start ticking the clock. Here, the index i tells us which index ticked. If there's a carry, that's the situation when we need to push the current element to the back. Otherwise, we're doing a swap and it's just a quick calculation to compute which index to swap with. Fix this little copy-paste error and then we're all set. This is a completely iterative permutations algorithm. The only thing left to do is error checking and to allow things that aren't lists. So, we take in an arbitrary iterable. Just make a copy of it into a tuple, Make default parameters and throw errors if anything's wrong. Then we just create a list of the same size as our iterable was. We use our algorithm to permutate the indices. And then we just use the indices to index into our tuple. So, basically once you can permute lists, then the whole thing is solved. But wait, you say. What about this code? Weren't we supposed to understand this code? It's finally time. We have all the pieces. Now we just need to see them fit together in this function. Here's the first side by side. And as you can see, the first part is basically the same. Except, they called their variable pool instead of items And they're not doing error checking. We call a helper function. They just paste it all into the main function. So, let's compare the helper functions. But first note that whenever the helper function does yield, we're always returning a tuple indexed by these indices into the items. And same thing on the right side. They're always yielding a tuple where they index into their items using the indices. They write it this way which is a little bit shorter. But it's actually making a copy of the indices every time they yield. So, I prefer to do it this way. But it's yielding the same things. Now let's compare our subroutine. Well, it doesn't look that similar. It looks like they're doing something different. We can sort of correspond some of the parts. Here, this is our push to back. And this is actually just another way to do push to back. And here, we're just swapping items. And here, they're just swapping items. They're using a negative index. But we're subtracting n from the tick value. So, it's the same thing as the negative index. So, those pieces are basically the same. But on the right side, they're doing this whole while for-else with an if and breaks in it. Oh, wait. That structure is our countdown code. Which is what we're looping over. Take a bit of a closer look at this. n is not being modified anywhere in this loop. This basically just says: If n is 0, then return. Otherwise, while True. In our countdown code, r ticks. That's the same definition as their cycles. And we have a while True with the exact same for-else return and breaks inside. And if you look closely, all this swapping and moving with the indices is completely independent of the iteration. None of the looping conditions, the n or the for i in range r, none of that depends on the indices. It only depends on the cycles. So, we really have the exact same thing. We have a while True. Then we have a for i in reversed range. We subtract 1 from our tick. We check if the tick is 0 and reset it if it is. Otherwise, we break. And if we didn't break and we get to the end, then we return. That's exactly our countdown code. The only difference is that we factored it out into a function. There we have it. This is functionally identical code. The only difference is that we factored out a function or two. Yes, it's technically more efficient if you don't have extra function calls. But remember, this is just expositional code. This isn't actually performance code. The real code was written directly as a C extension module. So, that's the end of our analysis of the code. And I just want to take a moment to step back. This code teaches us a few very important lessons that I hope you can learn from. Firstly, if you're considering authoring code that's very clever like this, then you need to be extremely careful. If you do something too clever, there's a decent chance that no one else that looks at the code will even attempt to understand it. This really highlights the importance of breaking your code up into consumable chunks. If they had just factored out this little piece, the countdown into a separate function, way more people would attempt to understand it. And way more people would understand it. Mentally, it's easy to separate the operations that you're doing on the list from this countdown ticking thing. They're completely separate independent things. So, don't mix them together in code like this. And second lesson: Don't be afraid to try to solve the problem yourself from first principles. Beyond using the most basic version of writing a recursive algorithm, none of these steps were really that big of a leap. We started by just counting solutions that was easy. We wrote the recursive algorithm. That's probably the hardest part. But if you have some experience doing that, it's not that much of a leap. It's the first and most straightforward algorithm that came up. Then we leveraged our recursive implementation to see what it was doing in terms of indices and create an iterative version. In my mind, all this work combined is less work than just starting with this finished answer and trying to understand what it's doing. The whole thing felt very natural, building and discovering the algorithm from scratch. But going backwards, it's still confusing to look at. So, even when a problem looks hard, don't be afraid to give it a shot. Serious thanks to anyone who stuck around. As always, thank you to my patrons and donors for supporting me. I really appreciate your support. If you really enjoy my content, if you love these deep dives, if you want to hear more, please do consider subscribing to my channel and becoming a patron on Patreon. Don't forget to comment and slap that like button an odd number of times. See you next time.
