Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Q: What’s the unknown?

A: The next permutation of the current sequence.

Q: What’re the data?

A: An integer array representing a number.

Q: Any Constraints?

A: No extra memory allocation allowed. But I think it means extra memory proportional to the input size N. Besides, at the beginning of solving this problem, we can ignore this constraint.

Q: True. Now what’s the meaning of next permutation?

A: Hmm, I think it means the next number sequence of the current sequence in lexicographic order, e.g., (1,2, 5, 3,4) -> (1,2, 5, 4,3), (1, 5, 3,4,2) -> (1, 5, 4,2,3) and (5, 4,3,2,1) -> (1,2,3,4,5).

Q: Now as a human being, how do you do this?

A: Eh..just think of the smallest number comprised of these digits that is greater than the current sequence. If there is none, we go back to the smallest possible number in all permutation.

Q: OK, but a computer can’t just “think of” the next number. Now how would a computer do that?

A: Hmm, I think we probably need to start with the least digit on the right side. But what next?

Q: Look at the example you listed above. What did you do with each example?

A: In (1,2, 5, 3,4) -> (1,2, 5, 4,3), I start with 4 and look at its left digit, 3. Since 3 < 4, I switch them. Hmm this works for all cases where the second digit is less than the first one. In (1, 5, 3,4,2) -> (1, 5, 4,2,3), I can’t switch 4 and 2 since (1,5,3,2,4) precedes (1,5,3,4,2). Well 3 < 4, I could switch them to get (1,5,4,3,2) but that’s not the correct answer. Hmm…

Q: So how do you get from (1,5,4,3,2) to (1,5,4,2,3)?

A: I could just switch 3 and 2.

Q: OK, what about (1,5,3,4,2,0) to (1,5,4,0,2,3)?

A: Hmm if I switch 3 and 4, I get (1,5,4,3,2,0). To get (1,5,4,0,2,3), I need to reverse 3,2,0 to 0,2,3. OK, I guess we should do like this: scan from the right, find the first digit at index Ind that is less than its previous digit, switch them and reverse the sequence to the right side of Ind.

Q: Well, almost there, but not yet. What about (1,6,3,5,4,0)? According to your algorithm above, the next permutation becomes (1,6,5,0,4,3) while it should be (1,6,4,0,3,5). See the problem?

A: Hmm, so 3 should be the switch point. I got that right, but it should switch with 4 instead of 5. Ah, so 3 should switch its ceiling in the sequence on its right side! We need to go back to find it and swap. Then do the reverse operation.

Q: Correct, what about the time complexity?

A: We scan the sequence and once find the switch point, we go back and find its ceiling, then switch and reverse. End of story. So it’s actually O(n), an linear time algorithm.

Code on github:


Enhanced by Zemanta