Python's permutations function (deep dive & implementation)

How does Python compute permutations?

It's not as complex as you might think! In this video we take a very deep dive and explain the code that Python uses to compute permutations.

SUPPORT ME ⭐
---------------------------------------------------

Top patrons and donors: Jameson, Laura M, Vahnekie, Dragos C, Matt R, Casey G, Johan A, John Martin, Jason F, Mutual Information, Neel R

BE ACTIVE IN MY COMMUNITY 😄
---------------------------------------------------

CHAPTERS
---------------------------------------------------
0:00 Intro
0:41 itertools permutations
2:14 counting permutations
2:58 recursive permutations
8:53 recursion limit
10:25 eliminating recursion
11:31 countdown ticker
14:01 iterative permutations
14:24 allowing any iterable
14:56 comparing ours vs itertools

[grmancool]

jesus I'll need to watch this 3 or 4 times to understand it lmao

[ran_red]

When I started learning to program, near the beginning of the process, I made the colossal mistakes of:

- thinking I was better than I actually was at the time
- stumbling upon this code

It was an unbelievably humbling experience. My delusions of "Oh, I am doing ok actually!" got nope'd to oblivion.

[Gaivs]

9:49 I would actually argue that on a machine code level everything is neither iterative nor recursive, as everything is just about jumping from one instruction to some new instruction (so that loops and conditions are also essentially the same). Still I'd argue that recursion is closer to what the machine code does than iterations, as the jumps are more explicit. Languages like Elixir don't even use loops, instead always using recursion, which (at least to me) implies that recursion is the more fundamental than iterating. Furthermore, all iterative algorithms can be converted into recursive algorithms, but not the other way around (e.g. Ackerman).

I'm not arguing that iterating isn't an extreme useful "thing", nor that iterating isn't the most effective way of handling data, just giving my two cents on the fundamental of computers 😅

Really great video, love watching everything you make 👏

[thewalkthroughmaking]

That was amazing! Would you mind ever doing a video about that "build your own in memory stack over the system maintained function stack" general solution?

[nocturnomedieval]

Hi James. Great topic choice. There is a bunch of algorithms to do this like Heap, JST, Knuth lexicographic ( yes, the Turing award and J.von Neumann Prize winner, creator of Tex, The art of computer programming and precursor of literate programming concept). The nice part here is I learned today about Python recursion limit.

[ren]

I've (re-)learned that being able to understand the code logic and convey the logic to the crowd is of similar (if not equal) importance as well!
thank you James.

[fyellin]

I’ve stared at that code so many times without being able to figure out how it worked. Thanks for the clear explanation. Now it’s time for me to try and see if I can now understand combination and combination_with_replacement.

[gardnmi]

This is when I go back to the client and convince them they only need to know the number of permutations vs actually seeing them.

[logicweaver]

Yeah, understanding logic from code is much more difficult than understanding logic then coding it.
Is there any doc which details concepts behind python implementations?

[CFEFABB]

I like this deriving blah from first principals stuff. I have leveled up so many skills trying to derive things from first principals. My first object oriented project was trying to create a type hierarchy for mathematics, that included kind of an abstract syntax tree. Didn’t know it at the time but my BinaryOperation class that contained left and right children taught me a lot about how to code.

[Illdos]

I think part of the issue is that those variable names do not help. I decided to poke at the code for a bit and I think just a couple of comments and naming things in a way to try give the reader a mental framework of what we're trying to do could go a long way. I'm wondering if presenting the code in this way makes it more intelligible or not (I could be completely off here, but I figured I would try. A YouTube comment is probably not the best place for raw python code):

def permutations(iterable, length=None):
# Lets treat our iterable as the occupants of rooms in a hotel.
# Our goal is to get every arrangement of guests in our first [length] rooms.

rooms = tuple(iterable)
occupancy = len(rooms)
length = occupancy if length is None else length

if length > occupancy:
return

guests = list(range(occupancy))
unvisited_rooms = list(range(occupancy, occupancy-length, -1))
yield tuple(rooms[guest] for guest in guests[:length]) # Unchanged permutation. Loop needs to make this yield every arrangement of indices.

while occupancy: # Run only if there are rooms
for guest in reversed(range(length)):
unvisited_rooms[guest] -= 1
if unvisited_rooms[guest] == 0:
guests[guest:] = guests[guest+1:] + guests[guest:guest+1]
unvisited_rooms[guest] = occupancy - guest
else:
visit = unvisited_rooms[guest]
guests[guest], guests[-visit] = guests[-visit], guests[guest]
yield tuple(rooms[guest] for guest in guests[:length])
break
else:
return

[AJMansfield]

Would it be possible for you to do a deep dive on the performance C implementation of an algorithm like this in the future? The C code is probably much more difficult to understand (using unguarded iteration and fun stuff like that) but I bet there are still some interesting insights you could gain from that too.

[Alche_mist]

For me, the transformation into iterative version is the largest leap. The recursive solution comes quite naturally to me, as that's what you do when you try to solve such problem (on a small set) in your head.

[GabrielSoldani]

Have you thought of contributing this refactor to the itertools module? And perhaps, if the C code is structured similarly, to the C code as well (where inlining and compiler optimizations could make it a zero cost abstraction)?

[failgun]

For potentially performance intensive functions like this one, the function call overhead in Python is appreciable. (not so much for C with inlining, however). But if you wanted a pure-Python permutation function, it will be a fair bit slower if you refactored loop code into (admittedly, nice and pythonic) convenience functions rather than unwrapping it all into one ugly loop as the itertools implementation has done.

I tested this using the combinations of n, r up to (5, 6) from the script on your github and found the convenient implementation to be 12% slower across 30, 000 trials. If you're writing a library like itertools, that might be too significant a loss to pay for readability, although if you do care about +/- 10% speed, don't implement your library all in Python, I guess.

[pj-nznm]

I loved this video, please make such kind of videos more.

[AngryArmadillo]

What a great way to do exposition on a scary topic 😅

[joseville]

9:28 Kind of a digression, but any tail recursive function can be converted into an iterative function (while loop) without use of a stack.

The recursive permutations function here however is not tail recursive, so something more clever happened to convert it into an iterative function.

[seansmith]

Great video! Insights at the end are spot on.

[mattlau]

it's really interesting to see the whole logic behind an algorythm