Permutations & Next Permutation

Source: Dev.to

Introduction

Permutations are a fundamental concept in problem solving and data structures (PS/DSA).
They appear in recursion, backtracking, combinatorics, graph traversal, interview problems, and optimization/state‑exploration tasks. Understanding permutations deeply also makes the Next Permutation problem trivial and intuitive.

A permutation is an ordered arrangement of elements.
For n distinct elements, the total number of permutations is n!.

Example

For the array:

[1, 2, 3]

All permutations:

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

Order matters ([1,2] ≠ [2,1]). Exploring permutations means exploring all possible states.

Why Permutations Matter in PS / DSA

Permutations train you in:

• Recursion
• Backtracking
• State restoration
• Depth‑first search
• Choice–Explore–Undo pattern

Many advanced problems are built on permutations:

• N‑Queens
• Sudoku
• Subsets & combinations
• K‑th permutation
• Word arrangements

Backtracking Template

1. Choose – swap or mark an element as used.
2. Explore – recursive call.
3. Unchoose – undo the swap / unmark (backtrack).

The classic in‑place backtracking algorithm:

function permute(nums) {
  const result = [];

  function backtrack(index) {
    if (index === nums.length) {
      result.push([...nums]);
      return;
    }

    for (let i = index; i  a - b);
  const result = [];
  const used = new Array(nums.length).fill(false);

  function backtrack(path) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i  0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;

      used[i] = true;
      path.push(nums[i]);
      backtrack(path);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return result;
}

Result for [1,1,2]:

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

Next Permutation

Goal: Find the smallest permutation Q such that Q > P in lexicographical (dictionary) order.

Lexicographical Order

For [1,2,3] the permutations in order are:

123
132
213
231
312
321

The next permutation is simply the next row.

Algorithm Overview

function nextPermutation(nums) {
  // 1. Find the pivot
  let i = nums.length - 2;
  while (i >= 0 && nums[i] = 0 && nums[i] >= nums[i + 1]) {
    i--;
  }

  if (i >= 0) {
    // 2. Find successor
    let j = nums.length - 1;
    while (nums[j] <= nums[i]) {
      j--;
    }
    // 3. Swap
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  // 4. Reverse suffix
  reverse(nums, i + 1);
}

function reverse(arr, start) {
  let l = start,
      r = arr.length - 1;
  while (l < r) {
    [arr[l], arr[r]] = [arr[r], arr[l]];
    l++;
    r--;
  }
}

The algorithm works correctly even with duplicate values because lexicographical comparison naturally handles them.

Examples

• [1,1,2] → [1,2,1] → [2,1,1] → back to [1,1,2] after another call.
• [3,2,1] (largest permutation) → no pivot found → reverse whole array → [1,2,3] (smallest permutation).

Comparison Table

Common Pitfall: Forgetting to Backtrack

When generating all permutations, failing to restore the previous state (swap back or unmark) leads to incorrect results or duplicated permutations. The backtrack step is essential to explore each branch independently.

Summary

• Permutations teach exhaustive state exploration via recursion and backtracking.
• Backtracking emphasizes the choose → explore → unchoose pattern, crucial for many combinatorial problems.
• Next Permutation demonstrates a minimal greedy change to move forward one step in lexicographic order, using O(1) extra space.

Both techniques are essential tools in a problem‑solver’s arsenal. 👍