Coding Interview Problem: Permutation Generator

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: jg.gg/permutation-generator-co...

[@lamduong5701]

Yo bro how are you writing this on the glass backward?

[@cwagnello]

Your comment at 17:12 is exactly the problem I've encountered in some interviews in Silicon Valley.

[@PrashanthG]

+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.

[@egor.okhterov]

We can find the number to swap in log(n) time. The tail is sorted in decreasing order, so we can search in it with binary search (or better use lower_bound).

[@twiho]

True, though that doesn't change the worst case complexity :-/

[@andrewfarley6794]

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

[@egor.okhterov]

We also should check for the case when we have size() == 1.

[@alexsavul]

hey Jackson. thanks for your awesome coding videos. There's one thing I didn't get that's right at the end of the video. You say that this problem is a bad interview question and that the best interview question is one that is not so puzzley. And the you say that it's absolutely the king of question one might get from a algorithmic company but I'm not sure to which kind of question you refer to

[@vaibhavbansal3030]

Permutations by themselves are very useful for use cases when you have to travel all possible paths (all combinations). I used them in a big project. But yeah, no one needs to write them from scratch coz most of the langs have support for them out of the box, itertools being one for python. But as per usage, its very useful for many domains. Anyway, I agree with you that interviews seem to be testing any thing and everything these days.

[@CarrotCakeMake]

The problem with your solution is that you don't prove that it is correct. "Noticing" things and "proving" things are very different. Can you actually prove that this produces all permutations, or do you just hope that it does?

[@tyler7069]

This presentation style is fresh as fuck

[@werewolf218961]

Love your approach man! Should make more videos

[@MarcoSuma]

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 ?

[@trident8638]

man, do you write characters inverted? while teaching?

[@user-ct9uo3gr2n]

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!

[@JackPunter2012]

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?

[@nicolatesla4491]

Thanks for the video but the audio is really bad.

[@jackson-gabbard]

It really is! I'm pretty unhappy with it too. If it's any consolation, I bought a new microphone which should result in much better audio for the next one. Thanks for hanging in there and for the feedback.

[@nicolatesla4491]

Excellent. I could really enjoy your channel with better audio. Keep up the good work!

[@Osunwrites]

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

[@thevikin9b]

Hey, I like the videos and I will keep watching when you upload new ones! Actually, I wonder why this permutation trick works... Coding the solution is easy, but I would like to know if there is something scientific behind the "find, swap, reverse" part.

[@ia9115]

a little advice: start with the problem first. people bait on that much then on bla-bla

[@Antox68]

Since the numbers are sorted why not binary search for *larger ?

[@daemonelectricity]

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.

[@iakashx]

your video is awesome. I was expecting better sound quality. It is kinda echoing sound. ;/

[@criticism09]

thanks for the video. The audio quality is not good and the background music is not helping

[@RonnyPfannschmidt]

this example should really be done in terms of a generic algorithm and iterators (see std::next_permutation)

[@jackson-gabbard]

Super true. This is my first attempt at actual algorithmic coding in C++ beyond trivial little experiments. Next go 'round I'll use more modern C++ techniques.

[@DiogoNeves]

Jackson Gabbard I'm at min 13, sorry if you fix it later but, on the point of iterating, shouldn't the check for base.begin happen before the check for decrease or it'll be out of bounds? Also, it shouldn't have the * when checking against begin because they're both iterators. Awesome video as always :) do you ever work from a co-working space or cafe or somewhere public in London? I'd love to say hi one day and thank you for the help :) Edit: ok, just noticed you return when at the beginning and isn't dangerous :)

[@alengm]

Diogo Neves if base has less than 2 elements, then decrease would be out of bounds before the loop starts.

[@EvaRevre]

I guess this example in an interview can show if you understood and are able to use recursion. The problem can be solved easily with a recursive call and a rest array of still available numbers. In each recursion step take the already build list with all combination of rest list and continue so, until rest list is empty. Start with an empty build list and a full rest list like rec( [], [1,2,3,4,5]) the results will be ordered length lexigographical too. jsfiddle.net/okukmf2m/

[@giorgospappas9101]

"Who's gonna use this for anything?" I need it to build an A.I. for a game....:P

[@balintcsala7487]

Or you know, start counting in base n and throw out every number with repetition...

[@IDCMI]

I really like your videos, the way of making and the information. However here goes my smart and nerdy comment: At 12:28 you say you're avoiding the off by 1. Two things to notice: #1, because the check on the left hand side has already been done, you may have already accessed memory out of bounds for collections of size 1 or smaller. (This might be smaller than decrease +1, for example 0, effectively skipping the break condition), afterwards swap will write literally anything anywhere. (DRAGONS) #2, even worse potentially, you compare a pointer to the value next. Writing this in such a low level language makes all those unicorns appear! (And all of this with a single star) That way, an attacker could swap the 1 with whatever is in the stack before the array, this might be a pointer or some other sensitive information. Then you'll print the list and get it returned. :) Alternatively you move 1 to the return address of the swap function and everything explodes. Both of those are security flaws and you managed to pack both of them in a single line. (Not attacking you or anything, it's just nice to see again why nobody should code in c) To be on the save side, .at() on a vector definitely does bounds checking. Keep up the good channel. It's fun! edit: #2 would probably not even compile with a recent/decent compiler, #1 may throw an assertion error, at least in debug, so with modern compilers it should be fine. Fix the tools, not the language...

[@ranjitarajkumari8746]

My 🔥🔥 topic..!!

[@jasdeepsinghgrover2470]

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

[@andreslizondro01]

Statham teaching C++. Sounds good!. Thanks for the video.

[@gardoversuso]

I have to give it to you in writing code mirrored in screen. :)

[@DrDrROSCH]

im pretty sure he is mirroring the image later on in editing ...

[@superitgel1]

He's not. And he isn't left handed.

[@serdarbaykan2327]

wait..but..how.. are you really writing inverted???

[@xchrisbradley]

When he said "Hungarian notation" I legit almost left the video lol

[@deacon1981]

whats wrong with hungarian notations?

[@davidharmeyer3093]

"You can't teach a java script programmer to code"

[@dysonlu]

"You can't teach a C++ programmer to think differently."

[@ranjitarajkumari8746]

Request to upload coding a new topic.

[@ajaypeddada2981]

Is he... is he writing backwards?

[@torrancedavenport8346]

Javascript does have generators.

[@jtt3030]

there is one mistake. i see when you go to swap the tail to ascending order it should be while (left > right )

[@LightningXThunderVlogs]

yes

[@bineetagupta]

Hi Jackson, is it possible if you can do some algo-solving exercises in C Language? Thanks!

[@sravanvedala7811]

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...

[@tc4877]

Honestly, and no offense to the video poster, but he's not a very good teacher. He's breaking the cardinal rule of teaching (among other fields); K.I.S.S. (Keep It Simple, Stupid). Throwing out a lot of big words and techno-jargon may seem impressive to onlookers, but it isn't an effective way of getting your message across. Pair this with the fact that he assumes knowledge that his audience may not have and it makes for a lot of blank stares.

[@tarcal87]

Video starts at 2:50...

[@schan263]

The background music is distracting.

[@gnskranthikumar8544]

how could he write in reverse

[@shanepanchot8681]

He just mirrors the footage

[@hsn81321]

@how?

[@superitgel1]

He can't, and he's not left handed. @Hasan Tahan photoshop aka Adobe aftereffects

[@vish4544]

Do you know! He's writing backwards for us

[@SoftBreadSoftware]

Or more likely he writes normally and mirrors the video.

[@tarcal87]

Ha, lack of thinking outside the box / alternatives / edge cases / etc

[@expeng5861]

crazy guys, mirrow your video.

[@copyrightpolice3002]

time now 3:25am 07/13/2016 your subs 1243 your permutation generator 1234

[@johnmadsen37]

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.

[@tomladdus9264]

I agree, this is a terrible question for an interview.

[@hahahaspam]

# Ruby def gen(n) [*1..n].permutation end

[@yelnil]

Does that even return a generator? That returns everything doesn't it? What the question asks is to implement this: PermutationGenerator p {5}; p(); //prints 1,2,3,4,5 p(); //prints 1,2,3,5,4 ...

[@hahahaspam]

That ruby code returns an enumerator, which, when called "next" on, returns the next permutation. So it works pretty much like a generator. p = gen(5) p.next #=> [1,2,3,4,5] p.next #=> [1,2,3,5,4] ... For more, here's the docs on Array#permutation: ruby-doc.org/core-2.2.0/Array.html#method-i-permutation And here's the important part: "If no block is given, an Enumerator is returned instead.".

[@yelnil]

I stand corrected. But still it's missing the point, you're supposed to implement it. C++ has std::next_permutation(...) which does what you did in the same number of lines.

[@hahahaspam]

"But still it's missing the point, you're supposed to implement it." Well of course you're supposed to be able to implement it. That doesn't mean you shouldn't know other solutions. While there are classic tradeoffs between time and space, there is also the tradeoff between being able to understand and deal with code and how efficient that code is. Thus, for the times when code need not be efficient, it would be wrong to write a less readable and less understandable solution to a problem.

[@prestonhansen49]

but you realize that no interviewer is going to accept this as an answer, right? if this was for your job, then yes, that's exactly what you'd do, but nobody is going to say "hey sort this list" and accept std::sort(list.begin(),list.end()) as an answer.

[@ranjitarajkumari8746]

C++ really sucks.. nice 🔥 handwriting..

[@marm4286]

Lol @9:10

[@garrettguitar6583]

Why is your voice echoey? kzbin.info/www/bejne/jGjLeaimqdmtjM0 What are you trying to explain where you say the reverse of 3,5,4,2,1 = 4,1,2,3,5? The reverse of 3,5,4,2,1 = 1,2,4,3,5. Quite obviously. So back to the title of the video… Permutation generator... How do I write one?