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.

Practice

1. What does the process of generating all permutations of an array mean?

easy

A. Finding the maximum element in the array

B. Sorting the array in ascending order

C. Listing all possible orders of the array elements

D. Removing duplicate elements from the array

Solution

1. Step 1: Understand permutations

   Permutations are all possible ways to arrange elements in order.

2. Step 2: Apply to array elements

   Generating all permutations means listing every possible order of the array elements.

3. Final Answer:

   Listing all possible orders of the array elements -> Option C

4. Quick Check:

   Permutations = all orders [OK]

Hint: Permutations = all ways to arrange elements [OK]

Common Mistakes:

• Confusing permutations with sorting
• Thinking permutations remove duplicates
• Mixing permutations with finding max/min

2. Which of the following is the correct base case for a recursive function generating all permutations of an array arr of size n?

easy

A. if (start > n) { print(arr); return; }

B. if (start == n) { print(arr); return; }

C. if (n == 0) { return; }

D. if (start == 0) { print(arr); return; }

Solution

1. Step 1: Understand recursion base case

   The base case occurs when the start index reaches the array size, meaning a full permutation is formed.

2. Step 2: Match base case condition

   Condition start == n means all positions are fixed, so print the permutation and return.

3. Final Answer:

   if (start == n) { print(arr); return; } -> Option B

4. Quick Check:

   Base case when start equals array size [OK]

Hint: Base case: start index equals array length [OK]

Common Mistakes:

• Using start > n instead of start == n
• Printing when start == 0 (start of recursion)
• Missing base case leading to infinite recursion

3. What is the output of the following C code snippet?

void permute(int *arr, int start, int n) {
    if (start == n) {
        for (int i = 0; i < n; i++) printf("%d ", arr[i]);
        printf("\n");
        return;
    }
    for (int i = start; i < n; i++) {
        int temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;
        permute(arr, start + 1, n);
        temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {1, 2};
    permute(arr, 0, 2);
    return 0;
}

medium

A. 1 2 \n 2 1 \n

B. 1 2 \n 1 2 \n

C. 2 1 \n 1 2 \n

D. No output

Solution

1. Step 1: Trace first call permute(arr, 0, 2)

   Start=0, loop i=0 to 1. Swap arr[0] with arr[0], call permute(arr,1,2).

2. Step 2: Trace second call permute(arr, 1, 2)

   Start=1, loop i=1 to 1. Swap arr[1] with arr[1], call permute(arr,2,2). Base case reached, print "1 2".

3. Step 3: Backtrack and swap arr[0] with arr[1]

   Now arr = {2,1}. Call permute(arr,1,2) again, print "2 1".

4. Final Answer:

   1 2 2 1 -> Option A

5. Quick Check:

   All permutations of [1,2] printed [OK]

Hint: Swap and backtrack to generate permutations [OK]

Common Mistakes:

• Not swapping back after recursive call
• Printing incomplete permutations
• Confusing loop indices

4. Identify the error in the following code snippet that generates permutations of an array arr of size n:

void permute(int *arr, int start, int n) {
    if (start == n) {
        for (int i = 0; i < n; i++) printf("%d ", arr[i]);
        printf("\n");
        return;
    }
    for (int i = start; i < n; i++) {
        int temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;
        permute(arr, start + 1, n);
        // Missing swap back here
    }
}

medium

A. Missing swap back after recursive call causes incorrect permutations

B. Base case condition should be start > n

C. Loop should run from i = 0 to n

D. Printing inside base case is incorrect

Solution

1. Step 1: Understand swap and backtrack

   After swapping and recursive call, we must swap back to restore original array for next iteration.

2. Step 2: Identify missing swap back

   The comment shows swap back is missing, so array stays changed, causing wrong permutations.

3. Final Answer:

   Missing swap back after recursive call causes incorrect permutations -> Option A

4. Quick Check:

   Swap back needed to restore array [OK]

Hint: Always swap back after recursion to restore array [OK]

Common Mistakes:

• Forgetting to swap back after recursion
• Changing loop range incorrectly
• Wrong base case condition

5. Given an array arr = {1, 2, 2}, how many unique permutations will a correct algorithm generate that avoids duplicates?

hard

A. 6

B. 2

C. 4

D. 3

Solution

1. Step 1: Calculate total permutations without duplicates

   For 3 elements with two '2's, total permutations = 3! / 2! = 3.

2. Step 2: List unique permutations

   Unique permutations are: [1,2,2], [2,1,2], [2,2,1]. But careful with counting duplicates in generation.

3. Step 3: Consider correct algorithm avoiding duplicates

   Some algorithms generate 4 permutations including one duplicate if not careful, but correct unique count is 3.

4. Final Answer:

   3 -> Option D

5. Quick Check:

   Unique permutations = 3 [OK]

Hint: Use factorial formula with duplicates: n!/k! [OK]

Common Mistakes:

• Counting duplicates as unique permutations
• Ignoring duplicate elements in calculation
• Assuming all permutations are unique