Next Permutation of Array in DSA Python - Build from Scratch

Next Permutation of Array

📖 Scenario: You are working on a feature for a puzzle game that needs to find the next arrangement of numbers in a sequence. This helps the game show the next possible move to the player.

🎯 Goal: Build a program that finds the next permutation of a list of numbers. If the list is the highest possible order, it should reset to the lowest order.

📋 What You'll Learn

Create a list called nums with the exact values [1, 2, 3]

Create a variable called i to find the first decreasing element from the right

Implement the logic to find the next permutation of nums

Print the nums list after finding the next permutation

💡 Why This Matters

🌍 Real World

Finding the next permutation is useful in games, puzzles, and generating combinations or arrangements in tasks like scheduling or testing.

💼 Career

Understanding permutations helps in algorithm design, problem-solving, and coding interviews for software development roles.

1

Create the initial list

Create a list called nums with the exact values [1, 2, 3].

DSA Python

# Create the list nums with values [1, 2, 3]
# Your code here

Hint

Use square brackets to create a list and separate numbers with commas.

2

Find the first decreasing element from the right

Create a variable called i and set it to the index of the first element from the right where nums[i] is less than nums[i + 1]. Start from len(nums) - 2 and move left.

DSA Python

nums = [1, 2, 3]
# Find the index i where nums[i] < nums[i + 1] starting from the right
# Your code here

Hint

Use a while loop to move left until you find nums[i] < nums[i + 1].

3

Find the next permutation core logic

If i is not less than 0, create a variable j starting from len(nums) - 1 and move left until nums[j] is greater than nums[i]. Then swap nums[i] and nums[j]. Finally, reverse the sublist from i + 1 to the end of nums.

DSA Python

nums = [1, 2, 3]
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
    i -= 1
# If i >= 0, find j and swap nums[i] and nums[j], then reverse nums[i+1:]
# Your code here

Hint

Swap the elements and reverse the tail part of the list to get the next permutation.

4

Print the next permutation

Print the nums list after finding the next permutation using print(nums).

DSA Python

nums = [1, 2, 3]
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
    i -= 1
if i >= 0:
    j = len(nums) - 1
    while nums[j] <= nums[i]:
        j -= 1
    nums[i], nums[j] = nums[j], nums[i]
nums[i + 1:] = reversed(nums[i + 1:])
# Print the nums list
# Your code here

Hint

Use the print function to show the final list.