Write a program to print all permutations of a given string | GeeksforGeeks

This video is contributed by Sephiri.
#geeksforgeeks

[WimpyWarlord]

This is so robotic, there is no intuition, no insight, basically dry running !
Partially helpful !

[adeshshetty]

I think the i =2 case for Level 1 has a small mistake. Swapping A[0] and A[2] of ABC will give CBA. The video says CAB. Let me know if I am mistaken.

[tushar]

vector<string> result;
sort(S.begin(), S.end());

do
{
result.push_back(S);
} while (next_permutation(S.begin(), S.end()));

return result;

[WafflerMark]

This video demonstrates two things seldom seen in other explanations, and that makes this great! 1) The overlay of the translucent (low opacity) of the execution over the code, and 2) the inclusion of a detailed explanation of the execution. Well done; thank you!

[algotorials]

you can have explained recursion by showing the allocation and execution of stack for a single permutation or any reference video of stack allocation or execution.

[sander_bouwhuis]

1. This algorithm doesn't generate the permutations in sorted order, so I use a slightly different approach.
2. What is with all the negativity in the comments? I for one think you explain it very exhaustively. Thumbs up!

[ayushgupta]

best ever explanation ever i watch for backtracking

[TheAshishk]

+GeeksforGeeks I think the explanation is a little wrong. We are not backtracking from level 2 to level 1, as you mentioned at 2:18.
You said we again "SWAP A and A" and come back to the original configuration, but backtracking is done while "SWAPPING B and B again" and " SWAPPING B and C again", after than no backtracking is done but "i" gets incremented and becomes 2 in For loop and A gets swapped with B which results in "BAC".

Please check and explain me if i am understanding it wrongly.
Thank you

[DebashisSahoo]

Asking a sincere question, Please don't mind.
While calculating Time complexity of the algorithm, it's coming out to be N * N!
I am clear with N!
For N (That's taking to print the string each time) I am having doubt.
Generally printing of a string takes constant time.
Please justify.
Thank you in advance. You have done a great job.

[chinmaydas]

Very standard channel.. But don't know why very few subscribers.. people don't want to learn important difficult things.. want easy one..

[niksgupta]

In level 1, and i=2, it should be CBA instead of CAB ( as per the tree in the beginning).
Let me know if my understanding is wrong.

[pramodsrinivasan]

I think there is a typo in the video :
For i = 2,
swap(A, C)
permute(CBA, 1, 2) // instead of permute(CAB, 1, 2)
swap(C, A)

[vivs]

The way you've printed out Levels for each recursive call and dry run is very informative. Did you manually wrote this or used a piece of code to print out ? it would be very helpful in understanding recursion.

[chandrashekhar]

Regarding time complexity.I had a doubt, How can printing the string became O(N).it should be O(1).Please clarify!

[kaushaljhawar]

Nicely explained..
please add interview question asked by the company during interview.

[dharmikbatra]

why its n*n! ? if we are printing n times then it should be n + n! which eventually be n! only??

[manojdani]

I wrote the code with and without the backtracking step. Both programs produce all combinations correctly. The order is different. The program without backtracking created a sorted output vs. the one with backtracking did not create sorted output.(note the last two elements - CBA vs CAB) So I am failing to see the importance of backtracking? Is this really required here?

Code for reference
(without backtrack)
for(int i=posn;i<input.size();i++)
{
swap(input[posn], input[i]);
permute(input, posn+1);
}
Output:
ABC
ACB
BAC
BCA
CAB
CBA

(with backtrack)
for(int i=posn;i<input.size();i++)
{
swap(input[posn], input[i]);
permute(input, posn+1);
swap(input[posn], input[i]);
}
ABC
ACB
BAC
BCA
CBA
CAB

[rushikeshsatkar]

Best Explanation ever, Thank you for shearing your knowledge with us...!

[theindiancookbook]

can you please use a better mic from next time, audio volume is low and clarity is also not good.

[johnk]

Best explanation of this (permutation) and backtracking. I see now that backtracking is analogous to a depth-first traversal of a tree.

I still don't quite understand Heap's permutation algorithm, which only has one swap instead of two, and that swap is slightly different depending on the even-odd parity of the string; I would appreciate if someone could respond with a sort of comparison of this with Heap's algorithm for permutations, which is very similar.