sko.kr

Algorithms - 20. Permutations

algorithmsbacktrackingpermutationscombinatoricsrecursive-algorithms
By sko•10/9/2025•9 min read

When to use Permutation Algorithms

Use permutation algorithms when you need to generate all possible orderings of a set of distinct elements. While most commonly used for generating arrangements, they can be adapted for:

  • All possible orderings of a sequence (classic use case)
  • Scheduling problems where order matters
  • Password generation from a set of characters
  • Path finding through all points exactly once (traveling salesman variations)
  • Game state exploration where moves can be made in different orders
  • Testing all possible execution orders of operations
  • Any problem where you need to systematically explore all arrangements

Example problem

Task Assignment: Given 3 tasks [A, B, C] that need to be completed in some order, generate all possible ways to schedule them.

After generating all permutations:

  • Schedule 1: [A, B, C] - Do A first, then B, then C
  • Schedule 2: [A, C, B] - Do A first, then C, then B
  • Schedule 3: [B, A, C] - Do B first, then A, then C
  • Schedule 4: [B, C, A] - Do B first, then C, then A
  • Schedule 5: [C, A, B] - Do C first, then A, then B
  • Schedule 6: [C, B, A] - Do C first, then B, then A

Answer: 6 different schedules (3! = 6 permutations)

What Permutation Generation Actually Does

Permutation generation systematically builds all possible orderings by making a series of choices. It provides exactly two approaches:

  1. RECURSIVE/BACKTRACKING: Build permutations by choosing elements one at a time
  2. ITERATIVE: Build permutations by inserting elements into all possible positions

Think of it like arranging books on a shelf:

  • Recursive: "Pick a book for position 1, then pick from remaining for position 2, etc."
  • Iterative: "Place book 1, then insert book 2 in all possible positions, then insert book 3 in all positions of each arrangement"

How the Approaches Work

RECURSIVE APPROACH - "Choose-Explore-Unchoose"

When generating permutations recursively:

  1. Choose an element for the current position
  2. Recursively generate permutations for remaining elements
  3. Backtrack by unchoosing the element
  4. Try the next element in that position

ITERATIVE APPROACH - "Insert at All Positions"

When generating permutations iteratively:

  1. Start with empty permutation
  2. For each element, take all existing permutations
  3. Insert the element at every possible position in each permutation
  4. These new permutations become your set for the next element

When These Operations Happen

The key insight is that each element must appear exactly once in each permutation:

// RECURSIVE: Fix position, try all elements
function generatePermutations(elements) {
  // For position 0, try element A, then B, then C
  // For position 1, try remaining elements
  // Continue until all positions filled
}

// ITERATIVE: Fix element, try all positions
function generatePermutations(elements) {
  // Take element A, insert at position 0
  // Take element B, insert at positions 0 and 1
  // Take element C, insert at positions 0, 1, and 2
}

The beauty is that both approaches explore the same solution space - just in different orders!

Single most important insight

Every permutation is uniquely defined by the series of choices made at each position - and by systematically exploring all choices (either which element for each position, or which position for each element), we guarantee generating all n! permutations exactly once.

Mental note: The algorithm's genius lies in viewing permutations as a decision tree. At each level, we decide either "which element goes in this position" (recursive) or "where to insert this element" (iterative). By exploring all branches of this tree systematically, we automatically generate every possible ordering without duplicates or omissions.

Decision Framework

The two approaches make different but equivalent decisions:

Recursive Approach - Position-Based Decisions:

  • For each position: "Which available element should go here?"
  • Number of choices decreases as we go deeper (n, then n-1, then n-2...)
  • Total paths: n × (n-1) × (n-2) × ... × 1 = n!

Iterative Approach - Element-Based Decisions:

  • For each element: "In which position should I insert this?"
  • Number of positions increases as we process elements (1, then 2, then 3...)
  • Total permutations: 1 × 2 × 3 × ... × n = n!

Code

// === RECURSIVE APPROACH: Backtracking ===
function permutationsRecursive(elements) {
  const allPermutations = [];
  const currentPermutation = [];
  const elementUsedFlags = new Array(elements.length).fill(false);

  function buildPermutations() {
    // Base case: completed a full permutation
    const isPermutationComplete = currentPermutation.length === elements.length;
    if (isPermutationComplete) {
      // Save a copy of this complete permutation
      const completedPermutation = [...currentPermutation];
      allPermutations.push(completedPermutation);
      return;
    }

    // DECISION FRAMEWORK: Choose element for current position
    // Try placing each unused element in the current position
    for (let elementIndex = 0; elementIndex < elements.length; elementIndex++) {
      const elementAlreadyUsed = elementUsedFlags[elementIndex];
      if (elementAlreadyUsed) {
        continue; // Skip to next element
      }

      // Make choice: place this element in current position
      const chosenElement = elements[elementIndex];
      currentPermutation.push(chosenElement);
      elementUsedFlags[elementIndex] = true;

      // Explore: build rest of permutation with remaining elements
      buildPermutations();

      // Backtrack: remove element to try different choice
      currentPermutation.pop();
      elementUsedFlags[elementIndex] = false;
    }
  }

  buildPermutations();
  return allPermutations;
}

// === ITERATIVE APPROACH: Insert at All Positions ===
function permutationsIterative(elements) {
  // Start with one empty permutation
  let currentPermutations = [[]];

  // Build permutations by processing one element at a time
  for (const elementToInsert of elements) {
    const permutationsWithNewElement = [];

    // Take each existing partial permutation
    for (const existingPermutation of currentPermutations) {
      // DECISION FRAMEWORK: Where to insert new element?
      // Try inserting at every possible position
      const numberOfPositions = existingPermutation.length + 1;

      for (
        let insertPosition = 0;
        insertPosition < numberOfPositions;
        insertPosition++
      ) {
        // Create new permutation with element at this position
        const permutationCopy = [...existingPermutation];
        permutationCopy.splice(insertPosition, 0, elementToInsert);

        // Save this new permutation
        permutationsWithNewElement.push(permutationCopy);
      }
    }

    // All permutations now include the new element
    currentPermutations = permutationsWithNewElement;
  }

  return currentPermutations;
}

// === CLEANER RECURSIVE: Using Swapping ===
function permutationsSwapping(elements) {
  const allPermutations = [];

  function generatePermutationsFromPosition(currentPosition) {
    // Base case: all positions have been filled
    const allPositionsFilled = currentPosition === elements.length;
    if (allPositionsFilled) {
      // Save a copy of current arrangement
      const completePermutation = [...elements];
      allPermutations.push(completePermutation);
      return;
    }

    // DECISION FRAMEWORK: Which element for current position?
    // Try each remaining element (from currentPosition to end)
    for (
      let candidateIndex = currentPosition;
      candidateIndex < elements.length;
      candidateIndex++
    ) {
      // Swap candidate element into current position
      const elementAtCurrentPos = elements[currentPosition];
      const candidateElement = elements[candidateIndex];
      elements[currentPosition] = candidateElement;
      elements[candidateIndex] = elementAtCurrentPos;

      // Generate permutations with this choice fixed
      const nextPosition = currentPosition + 1;
      generatePermutationsFromPosition(nextPosition);

      // Backtrack: restore original arrangement
      elements[candidateIndex] = elements[currentPosition];
      elements[currentPosition] = elementAtCurrentPos;
    }
  }

  const startPosition = 0;
  generatePermutationsFromPosition(startPosition);
  return allPermutations;
}

// === EXAMPLE USAGE: Task Scheduling ===
const tasks = ["A", "B", "C"];

console.log("=== Recursive Backtracking ===");
const schedulesRecursive = permutationsRecursive(tasks);
console.log(`Generated ${schedulesRecursive.length} schedules:`);
schedulesRecursive.forEach((schedule, index) => {
  const scheduleNumber = index + 1;
  const scheduleDisplay = schedule.join(" → ");
  console.log(`  Schedule ${scheduleNumber}: [${scheduleDisplay}]`);
});

console.log("\n=== Iterative Building ===");
const schedulesIterative = permutationsIterative(tasks);
console.log(`Generated ${schedulesIterative.length} schedules:`);
schedulesIterative.forEach((schedule, index) => {
  const scheduleNumber = index + 1;
  const scheduleDisplay = schedule.join(" → ");
  console.log(`  Schedule ${scheduleNumber}: [${scheduleDisplay}]`);
});

console.log("\n=== Recursive with Swapping ===");
const tasksCopy = [...tasks]; // Preserve original array
const schedulesSwapping = permutationsSwapping(tasksCopy);
console.log(`Generated ${schedulesSwapping.length} schedules:`);
schedulesSwapping.forEach((schedule, index) => {
  const scheduleNumber = index + 1;
  const scheduleDisplay = schedule.join(" → ");
  console.log(`  Schedule ${scheduleNumber}: [${scheduleDisplay}]`);
});

// Output for all three approaches:
// Generated 6 schedules:
//   Schedule 1: [A → B → C]
//   Schedule 2: [A → C → B]
//   Schedule 3: [B → A → C]
//   Schedule 4: [B → C → A]
//   Schedule 5: [C → A → B]
//   Schedule 6: [C → B → A]

Doubt buster

Common doubt: "Why does the iterative approach generate permutations in a different order than the recursive approach? Are we missing some permutations or generating duplicates?"

Why you might think there's a problem

When you run both algorithms, you get the permutations in different orders:

Recursive order:         Iterative order:
[A,B,C]                 [C,B,A]
[A,C,B]                 [B,C,A]
[B,A,C]                 [C,A,B]
[B,C,A]                 [A,C,B]
[C,A,B]                 [B,A,C]
[C,B,A]                 [A,B,C]

This looks confusing - they're completely different! You might worry that one algorithm is wrong.

Why this thinking is wrong

Both algorithms generate the exact same SET of permutations - just in different orders!

The key realization: The order in which we generate permutations doesn't matter as long as we generate all of them exactly once.

Understanding the different generation orders

Recursive approach builds like a decision tree:

                     []
          /          |          \
        [A]         [B]         [C]     (choose first element)
       /   \       /   \       /   \
    [A,B] [A,C] [B,A] [B,C] [C,A] [C,B] (choose second element)
     |     |     |     |     |     |
   [A,B,C][A,C,B][B,A,C][B,C,A][C,A,B][C,B,A] (choose third element)

Iterative approach builds by insertion:

Start: [[]]

Add A: [[A]]  (only one position to insert)

Add B: [B,A]  (B at position 0)
       [A,B]  (B at position 1)

Add C: [C,B,A] (C at position 0 of [B,A])
       [B,C,A] (C at position 1 of [B,A])
       [B,A,C] (C at position 2 of [B,A])
       [C,A,B] (C at position 0 of [A,B])
       [A,C,B] (C at position 1 of [A,B])
       [A,B,C] (C at position 2 of [A,B])

Concrete verification: Both generate all n! permutations

For n=3, we expect 3! = 6 permutations. Let's verify both algorithms generate exactly these 6:

All possible permutations of [A,B,C]:

  1. A before B before C: [A,B,C] ✓ (both algorithms generate this)
  2. A before C before B: [A,C,B] ✓ (both algorithms generate this)
  3. B before A before C: [B,A,C] ✓ (both algorithms generate this)
  4. B before C before A: [B,C,A] ✓ (both algorithms generate this)
  5. C before A before B: [C,A,B] ✓ (both algorithms generate this)
  6. C before B before A: [C,B,A] ✓ (both algorithms generate this)

Both algorithms generate all 6 and only these 6 - no duplicates, no omissions!

Why the generation order differs

The fundamental difference is in how they explore the solution space:

Recursive (Depth-First):

  • Commits to first element, explores all permutations with that element first
  • Like saying "Let's see ALL schedules that start with A before trying B"
  • Natural for backtracking: go deep, then backtrack

Iterative (Breadth-First-Like):

  • Processes elements one at a time, expanding all partial solutions
  • Like saying "Let's place C in all possible positions of what we have so far"
  • Natural for building up: start small, grow systematically

The mathematical guarantee

Both approaches guarantee generating all n! permutations because:

Recursive guarantee:

  • We try each of n elements in position 1
  • For each, we try each of (n-1) remaining in position 2
  • For each, we try each of (n-2) remaining in position 3
  • Total: n × (n-1) × (n-2) × ... × 1 = n!

Iterative guarantee:

  • Element 1 can go in 1 position: 1 permutation
  • Element 2 can go in 2 positions each: 1 × 2 = 2 permutations
  • Element 3 can go in 3 positions each: 2 × 3 = 6 permutations
  • Total: 1 × 2 × 3 × ... × n = n!

The bottom line: Different generation orders are not a bug - they're a natural consequence of different exploration strategies. Both algorithms are correct and complete, just taking different paths through the same solution space. Use whichever approach makes more sense for your specific problem!

← Back to Blog