31_next_permutation

dz / leetcode / 31_next_permutation

Summary

A permutation of an array of integers is an arrangement of its members into a sequence or linear order. For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order). For example, the next permutation of arr = [1,2,3] is [1,3,2]. Similarly, the next permutation of arr = [2,3,1] is [3,1,2]. While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement. Given an array of integers nums, find the next permutation of nums. The replacement must be in place and use only constant extra memory.

Node Tree

• editorial
  • approach_1_brute_force
  • permutations_wikipedia
• intuition
  • largest_permutation
    • approach_2_single_pass
      • how_to_visualize_this
    • reverse_smallest_to_largest
      • approach_2_single_pass
        • how_to_visualize_this
    • smallest_permutation
      • reverse_smallest_to_largest
        • approach_2_single_pass
          • how_to_visualize_this
  • recursion_maybe
  • upfront_reading
    • next_permutation_def
  • what_does_4_look_like
    • sweep_to_swap_point
      • approach_2_single_pass
        • how_to_visualize_this
      • sweep_swap_ex
        • recursion_maybe
• URL

Nodes

URL
content	URL
hyperlink	https://leetcode.com/problems/next-permutation

intuition
content	intuition
children	largest_permutation, recursion_maybe (feels like it could be expressed recursively), upfront_reading, what_does_4_look_like

upfront_reading
content	Lots of upfront reading. Reading now.
children	next_permutation_def
parents	intuition

next_permutation_def
content	This is establishing a formal definition with examples. So it's basically saying there's an order (for integers, it's just their numerical values?), and you need to determine what the next largest one in the sequence is. There's also the edge case where there is no greater sequence and you "wrap-around" to the smallest permutation.
parents	upfront_reading

largest_permutation
content	"lexographically" speaking, a permutation ABC is greatest if A>=B>=C.
children	approach_2_single_pass (got this relationship), reverse_smallest_to_largest, smallest_permutation (ergo)
parents	intuition

smallest_permutation
content	Consequently, the smallest permutation ABC is A<=B<=C.
children	reverse_smallest_to_largest
parents	largest_permutation

reverse_smallest_to_largest
content	The smallest permutation can be obtained by reversing the order of the permutation. And vice versa.
children	approach_2_single_pass (interestingly, the solution here involved using this property)
parents	smallest_permutation, largest_permutation

what_does_4_look_like
content	These examples are all in 3. But what would 4 look like? Supposing I have 1234 (the smallest). What would the next one be? 1243 is my guess, because it feels like counting. 1324 comes next. then 1342, 1423, 1432, 2134, 2314.
children	sweep_to_swap_point
parents	intuition

sweep_to_swap_point
content	Okay, I'm seeing a pattern. Starting from the right, move until you hit a point where the left value is less than the right value. This left value becomes the swap point and swaps with the rightmost (least significant) value. Sort all the values to the right until they are in ascending order left to right.
children	approach_2_single_pass (on the right track), sweep_swap_ex (example.)
parents	what_does_4_look_like

sweep_swap_ex
content	Next point after 1243. rightmost is 3. the index at the value 2 is the swap point because 2<4. Swap to become 1342, then sort the last 2 indices to be 1324.
children	recursion_maybe (possibly expressed recursively?)
parents	sweep_to_swap_point

recursion_maybe
content	I belive the rightmost value will always be the least signficant value, and this will be swapped with some other value. In my previous attempt, I swapped, then sorted in two steps, but I bet you could recursively swap until some end condition is met.
parents	intuition, sweep_swap_ex

editorial
content	editorial
children	approach_1_brute_force, permutations_wikipedia (followup)

approach_1_brute_force
content	The brute force algorithm would be to generate all possible permutations in order, and find the next one. This one is only hypothetically introduced, as it would be exceedingly inefficient to practically use.
parents	editorial

approach_2_single_pass
content	I got far enough to understand that you needed to find a pair of values starting from the right where the right value is greater than the left value. I was incorrect that the rightmost value would be the value to swap. You actually take the leftmost value, and find the next largest value after that in the rightmost segment. The trickiest logical leap here was knowing how to reversing the rightmost segment after making the swap. Before the swap, everything up to the found left value is the greatest possible subset-permutation, which has the property A>=B>=C. Reversing this wraps-around to the smallest permutation CBA, C<=B<=A. Here's the tricky bit: when the swap between the left value and the next greatest value in the right segment happens, this property still holds.
children	how_to_visualize_this
parents	sweep_to_swap_point, largest_permutation, reverse_smallest_to_largest

how_to_visualize_this
content	There's a lot of intuition one needs to build up to understand this problem. I don't know if I could have made these leaps or have been able to do everything correctly.
parents	approach_2_single_pass

permutations_wikipedia
content	The "Permutations in Computing" section has a bit on this sort of problem called "Generation in lexicographic order", which is probably worth a read to better understand this.
parents	editorial
hyperlink	https://en.wikipedia.org/wiki/Permutation#Permutations_in_computing