Recursion-dictionary order(larger)

#1

https://ide.codingblocks.com/s/42813
This is my code for the problem.
In line 21, if I do not remove the comments for swap function, the test cases are being accepted.
but test cases fail when the swap function in line 21 is used.
Please guide.

#2

Is there a way where I can escape the unnecessary permutations which are lexographically smaller than the input string?

#3

Add the question link

#4

Ques link:
https://hack.codingblocks.com/contests/c/512/361

#5

Both backtrack and without backtrack will fetch you correct results but in different order. Try running the backtrack code for “abcd”. You will get all the required strings but string “adcb” is printed before string “adbc” if we backtrack. So its advisable to sort the final output.

#6

I have observed the same . But in spite of regular backtracking, why is adcb printed before?

#7

And is there any way I can escape the unnecessary permutations which are lexographically smaller than the input string?(in context to the recursion problem initially mentioned)

#8

You will get to know the reason if you dry run it.
abcd
when i = 1 and j = 3
We swap
adcb
At this step we get adcb before adbc because of backtrack

1 Like
#9

One way to escape unnecessary permutations is to:

  1. Begin with i = 0
  2. Swap it with j>i if s[i] < s[j].
  3. Now call the original permutation function that uses normal recursion with printing in base case
  4. Backtrack.
  5. Repeat this for all j
1 Like
#10

Got it. Thanks a lot .

#11

No problem keep coding and rasing doubts.

#12

One test case is failing
https://ide.codingblocks.com/s/47100

#13

Hey Akshay, as you are using the in-built next_permutation() it returns the output sequence in sorted order which is not required. So, you are supposed to solve this problem recursively.

For eg.
input:
bca

your code’s output :
cab
cba

but correct order should be:
cba
cab