The problem mentioned in the image is from the book EPI. It asks for a solution where one has to find all the permutations of a list containing distinct Integers. I will solve this problem by finding the next successive permutation of a given sequence of numbers.
I will continue to perform the next permutation until the successive permutations equals input list.
Here goes the solution, I perform the successive operations of next permutation on a list. The next permutation can be performed as follows:
- The principle is to identify the role of prefix and a suffix. Whenever a number is incremented say 245 -> 246, we find that there is a suffix part that changes significantly and the prefix changes minimally doesn’t at all (here prefix is 24 and suffix is the digit in 1s place).
- In case of a list of Integers eg. <1,5,9,4,3> a similar characteristics must follow. In this list, the suffix should change significantly and there will be a little change in the prefix.
- The next permutation for the above list is <1,9,3,4,5>. There has been a change and one can observe that there is a sorted operation in the last two elements. This should contribute to the suffix.
- Now on reading the solution provided in the book. The real understanding was unlocked. The steps include finding the index from which the successive numbers are decreasing. The integers from that index form the suffix.
- Then we swap the value of the last number in prefix with the the number that is greater than the number if suffix. After this step all we have to do is reverse the suffix.
- So, the list changes like this <1,5,9,4,3> here the decreasing sub-list which is a suffix is <9,4,3>. Now in the prefix the last number is 5. This will be swapped with 9, which yields: <1,9,5,4,3>. On reversing the suffix we have <1,9,3,4,5>.
The following code provides the correct implementation of the same. This solution was accepted in LeetCode OJ.
The complexity of this O (n! * n). There are n! permutations and n operations involved in computing the next permutation.