Next Permutation

Finding the next permutation of an array can be done through the following steps:

  1. Find the First Decreasing Element: Traverse the array from right to left and find the first number that is smaller than the number immediately to its right.

  2. Find the Next Larger Element: If a smaller number is found, then traverse the array again from right to left and find the first number that is larger than the found smaller number.

  3. Swap the Elements: Swap the smaller number with the found larger number.

  4. Reverse the Sub-array: Reverse the sub-array to the right of the original position of the smaller number.

  5. Sort if No Permutation Found: If no smaller number is found, then the array is sorted in descending order, and there is no next permutation. In this case, sort the array in ascending order.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        i = len(nums) - 2

        # Step 1: Find the first decreasing element
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:
            # Step 2: Find the next larger element
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1

            # Step 3: Swap the elements
            nums[i], nums[j] = nums[j], nums[i]

        # Step 4: Reverse the sub-array or Step 5: Sort if no permutation found
        nums[i + 1:] = reversed(nums[i + 1:])

This solution modifies the array nums in-place to contain the next permutation and uses constant extra memory.

The time complexity is (O(n)), where (n) is the length of the array, as all the steps involve linear traversals or operations on the array. The space complexity is (O(1)) as we are modifying the array in place and not using any additional space.

Identifying Problem Isomorphism

“Next Permutation” requires you to rearrange numbers into the lexicographically next greater permutation of numbers. If such an arrangement is not possible, it must be rearranged as the lowest possible order.

An approximate isomorphic problem is “Permutations II”, which requires generating all possible unique permutations from a collection of numbers. Both problems deal with permutations of an array, but the tasks are distinct.

A simpler problem is “Permutations”. Here, the task is just to generate all possible permutations from a collection of numbers without having to worry about duplicates or ordering.

A more complex problem is “Permutation Sequence”, where you’re given two numbers n and k, and have to return the kth permutation sequence. This requires a more intricate understanding of permutations and their orderings.

From simpler to more complex:

  1. “Permutations” - Only requires generating all permutations.
  2. “Next Permutation” - Requires finding the lexicographically next greater permutation.
  3. “Permutations II” - Requires generating all unique permutations, adding complexity with the consideration of duplicates.
  4. “Permutation Sequence” - Requires determining the kth permutation sequence, adding complexity with an additional parameter and the requirement to find a specific permutation sequence.

These share the theme of permutations but the specific tasks and conditions vary. This is an approximate mapping based on the shared theme.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        i = j = len(nums)-1

        while i > 0 and nums[i-1] >= nums[i]:
            i -= 1

        if i == 0:
            nums.reverse()
            return 

        while nums[j] <= nums[i-1]:
            j -= 1

        nums[i-1], nums[j] = nums[j], nums[i-1]        
        nums[i:]= nums[len(nums)-1:i-1:-1]

Problem Classification

Permutation

Language Agnostic Coding Drills

  1. Variable assignment

    • Learn how to create and assign values to variables.

  2. Lists

    • Understand what a list is, how to create one and access its elements.

  3. Basic Arithmetic operations

    • Learn how to perform basic arithmetic operations such as subtraction (-=) and addition.

  4. Loops (while loops)

    • Learn about loops in programming, focusing specifically on while loops.

  5. Conditional Statements (if)

    • Understand the if statement and how it’s used to make decisions in the code.

  6. Comparisons

    • Learn about comparison operators such as >, <=.

  7. Indexes in Lists

    • Understand how indexing works in lists, including negative indexing.

  8. List Slicing

    • Learn how to slice a list to get a subset of the list.

  9. List methods (reverse)

    • Learn about the reverse method that’s used to reverse a list.

  10. Multiple assignments

  • Understand how to swap values of variables or list elements in one line.
  1. Defining Classes and Methods
  • Understand how to define a class and methods, including the self keyword.
  1. In-place methods
  • Understand methods that modify data structures in-place without creating a new copy.

Here is the progression of difficulty:

  1. Variable assignment
  2. Basic Arithmetic operations
  3. Lists
  4. Indexes in Lists
  5. Conditional Statements (if)
  6. Loops (while loops)
  7. Comparisons
  8. Multiple assignments
  9. List Slicing
  10. List methods (reverse)
  11. Defining Classes and Methods
  12. In-place methods

Targeted Drills in Python

  1. Variable assignment
1
2
3

# Drill: Assign the integer value 10 to a variable named 'a'
a = 10
print(a) # Expected output: 10
  1. Basic Arithmetic operations
1
2
3

# Drill: Subtract 2 from 'a' and store the result back in 'a'
a -= 2
print(a) # Expected output: 8
  1. Lists
1
2
3

# Drill: Create a list 'b' with values 1, 2, 3, 4, 5
b = [1, 2, 3, 4, 5]
print(b) # Expected output: [1, 2, 3, 4, 5]
  1. Indexes in Lists
1
2

# Drill: Print the last element in list 'b'
print(b[-1]) # Expected output: 5
  1. Conditional Statements (if)
1
2
3
4
5
6

# Drill: If the last element in list 'b' is greater than 4, print 'Greater', else print 'Not Greater'
if b[-1] > 4:
    print('Greater')
else:
    print('Not Greater')
# Expected output: 'Greater'
  1. Loops (while loops)
1
2
3
4
5
6

# Drill: Print each element in list 'b' using a while loop
i = 0
while i < len(b):
    print(b[i])
    i += 1
# Expected output: 1, 2, 3, 4, 5 on new lines
  1. Comparisons
1
2

# Drill: Check if the value of 'a' is less than the first element of list 'b'
print(a < b[0]) # Expected output: False
  1. Multiple assignments
1
2
3

# Drill: Swap the values of the first and last element in list 'b'
b[0], b[-1] = b[-1], b[0]
print(b) # Expected output: [5, 2, 3, 4, 1]
  1. List Slicing
1
2
3

# Drill: Get a sublist from the second to the fourth element in list 'b'
sub_b = b[1:4]
print(sub_b) # Expected output: [2, 3, 4]
  1. List methods (reverse)
1
2
3

# Drill: Reverse the elements in list 'b'
b.reverse()
print(b) # Expected output: [1, 4, 3, 2, 5]
  1. Defining Classes and Methods
1
2
3
4
5
6
7
8

# Drill: Define a class 'MyClass' with a method 'print_hello' that prints "Hello"
class MyClass:
    def print_hello(self):
        print("Hello")

# create an instance of MyClass
obj = MyClass()
obj.print_hello() # Expected output: "Hello"
  1. In-place methods
1
2
3

# Drill: Using the sort() function, sort the elements in list 'b' in-place
b.sort()
print(b) # Expected output: [1, 2, 3, 4, 5]

title: Next Permutation excerpt: This article show how to generate next permutation using recursion. tags: two-pointers-moving-towards-each-other swap

The term lexicographically means alphabetically ordered. In this problem it means next greater permutation:

1,2,3 => 1,3,2 (This permutation is the next highest value)

Somehow we need to find the smallest increase that results in the next permutation.

If the permutation is: [3,2,1]

[3,1,2] [1,3,2]

[1,2,3,3] [1,3,2,3]

[1,2,3,4,5,6,7,8,9] [1,2,3,4,5,6,7,9,8]

We only need one swap operation to find the next biggest number. If the numbers are in descending order:

Pick the permutation that is in the last location and return it.

output = [[p1], ….. [pn]]

If the numbers in the input is in ascending order:

output = [[p1], [p2]]

The next permutation is the second permutation generated by the DFS.

Assumptions

  1. We cannot assume that the numbers are sorted.
  2. There could be duplicates
  3. We cannot modify the order in which the integers appear in the input.

Example 4 is the base case [x] => [x]

[1,2] => [2,1]

We need to find the next lexicographic permutation of the given list of numbers rather than the number formed by the given array.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

def reverse(nums, start)
  i = start
  j = nums.size - 1
  
  while i < j
    nums[i], nums[j] = nums[j], nums[i]      
    i += 1
    j -= 1
  end
end

# @param {Integer[]} nums
# @return {Void} Do not return anything, modify nums in-place instead.
def next_permutation(nums)
  i = nums.size - 2
   
  while (i >= 0 && nums[i + 1] <= nums[i])
    i -= 1
  end
  
  if i >= 0
    j = nums.length - 1
    while (j >= 0 && nums[j] <= nums[i])
      j -= 1 
    end
		
    nums[i], nums[j] = nums[j], nums[i] 
  end
  
  reverse(nums, i+1) 
end

nums = [1,5,8,4,7,6,5,3,1]
p next_permutation(nums)

Building Blocks

  • Two Pointers Moving Towards Each Other
  • Swap