Generate All Permutations of Array in DSA C

Mental Model

We want to list every possible order of the array elements by swapping them step by step.

Analogy: Imagine you have a set of different colored balls and you want to see every way to arrange them in a line by swapping their positions.

Array: [1, 2, 3]
Positions: 0  1  2
Start: ↑
We swap elements at positions to create new orders.

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Generate all possible orders of the array elements

Step 1: Start with index 0, swap element at 0 with 0 (no change)

[1, 2, 3]

Why: Fix first element and permute the rest

Step 2: Move to index 1, swap element at 1 with 1 (no change)

[1, 2, 3]

Why: Fix second element and permute the rest

Step 3: Move to index 2, swap element at 2 with 2 (no change), record permutation

[1, 2, 3]

Why: Reached end, record current order

Step 4: Backtrack to index 1, swap element at 1 with 2

[1, 3, 2]

Why: Try next possible element at position 1

Step 5: Move to index 2, swap element at 2 with 2 (no change), record permutation

[1, 3, 2]

Why: Reached end, record current order

Step 6: Backtrack to index 0, swap element at 0 with 1

[2, 1, 3]

Why: Try next possible element at position 0

Step 7: Repeat steps for index 1 and 2 to generate permutations starting with 2

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

Why: Generate all permutations starting with 2

Step 8: Backtrack to index 0, swap element at 0 with 2

[3, 2, 1]

Why: Try next possible element at position 0

Step 9: Repeat steps for index 1 and 2 to generate permutations starting with 3

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

Why: Generate all permutations starting with 3

Result:

All permutations:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Annotated Code

DSA C

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void printArray(int arr[], int size) {
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i < size - 1) printf(", ");
    }
    printf("]\n");
}

void permute(int arr[], int start, int end) {
    if (start == end) {
        printArray(arr, end + 1); // record permutation
        return;
    }
    for (int i = start; i <= end; i++) {
        swap(&arr[start], &arr[i]); // swap to fix element at start
        permute(arr, start + 1, end); // permute rest
        swap(&arr[start], &arr[i]); // backtrack to original
    }
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    permute(arr, 0, n - 1);
    return 0;
}

if (start == end) { printArray(arr, end + 1); return; }

record current permutation when fixed all positions

for (int i = start; i <= end; i++) {

try every element in current position

swap(&arr[start], &arr[i]);

fix element at start by swapping

permute(arr, start + 1, end);

permute remaining elements

swap(&arr[start], &arr[i]);

backtrack to restore original order

Output

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 1, 2]

[3, 2, 1]

Complexity Analysis

Time: O(n! * n) because there are n! permutations and printing each takes O(n)

Space: O(n) for recursion call stack and temporary swaps

vs Alternative: This backtracking approach is efficient compared to generating all permutations and filtering duplicates, which would be slower.

Edge Cases

empty array

prints nothing or empty permutation

DSA C

if (start == end) { printArray(arr, end + 1); return; }

array with one element

prints the single element as the only permutation

DSA C

if (start == end) { printArray(arr, end + 1); return; }

array with duplicate elements

generates permutations including duplicates; no filtering

DSA C

for (int i = start; i <= end; i++) { swap(&arr[start], &arr[i]);

When to Use This Pattern

When you need to list all possible orders of a set of items, use backtracking with swapping to generate permutations efficiently.

Common Mistakes

Mistake: Not swapping back after recursive call, causing wrong array state
Fix: Always swap back to original positions after recursion to backtrack

Mistake: Stopping recursion too early before fixing all positions
Fix: Only record permutation when start index reaches end index

Summary

Generates every possible order of array elements by swapping and backtracking.

Use when you want to explore all arrangements of a list or array.

The key is to fix one element at a time and permute the rest recursively.