Generate All Permutations of Array in DSA Python

Mental Model

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

Analogy: Imagine you have 3 different colored balls and want to see all the ways you can line them up on a shelf by changing their positions one by one.

[1, 2, 3]
 ↑
Start with the first element and try swapping it with each element including itself.

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 index 0 with itself

[1, 2, 3]

Why: Begin permutations by fixing the first element as 1.

Step 2: Move to index 1, swap element at index 1 with itself

[1, 2, 3]

Why: Fix second element as 2, continue to permute the rest.

Step 3: Move to index 2, swap element at index 2 with itself, record permutation

[1, 2, 3]

Why: Reached end, record current order as a valid permutation.

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

[1, 3, 2]

Why: Try new order by swapping second and third elements.

Step 5: Move to index 2, swap element at index 2 with itself, record permutation

[1, 3, 2]

Why: Reached end again, record this new permutation.

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

[2, 1, 3]

Why: Change first element to 2, explore permutations starting with 2.

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 with first element fixed as 2.

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

[3, 2, 1]

Why: Change first element to 3, explore permutations starting with 3.

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 with first element fixed as 3.

Result:

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

Annotated Code

DSA Python

from typing import List

def generate_permutations(arr: List[int]) -> List[List[int]]:
    result = []
    def backtrack(start: int):
        if start == len(arr):
            result.append(arr.copy())  # record current permutation
            return
        for i in range(start, len(arr)):
            arr[start], arr[i] = arr[i], arr[start]  # swap to fix element at start
            backtrack(start + 1)  # permute remaining elements
            arr[start], arr[i] = arr[i], arr[start]  # swap back to restore
    backtrack(0)
    return result

# Driver code
input_array = [1, 2, 3]
permutations = generate_permutations(input_array)
for p in permutations:
    print(p)

if start == len(arr):

Reached end of array, record current order as a permutation

arr[start], arr[i] = arr[i], arr[start]

Swap to fix element at current start index

backtrack(start + 1)

Recursively generate permutations for the rest of the array

arr[start], arr[i] = arr[i], arr[start]

Swap back to restore original order before next iteration

Output

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 2, 1]

[3, 1, 2]

Complexity Analysis

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

Space: O(n) for recursion stack and O(n! * n) for storing all permutations

vs Alternative: This backtracking approach is efficient compared to generating permutations by repeated insertions which can be more complex and slower.

Edge Cases

empty array []

Returns [[]] representing one permutation: the empty list

DSA Python

if start == len(arr):

array with one element [5]

Returns [[5]] as the only permutation

DSA Python

if start == len(arr):

array with duplicate elements [1, 1]

Returns all permutations including duplicates: [1,1] and [1,1]

DSA Python

No special guard; duplicates are handled naturally by swapping

When to Use This Pattern

When you need to list every possible order of items, use backtracking with swapping to generate all permutations efficiently.

Common Mistakes

Mistake: Not swapping back after recursive call, causing wrong array state in next iterations
Fix: Always swap back to restore original order after recursive call

Mistake: Appending the original array reference instead of a copy, leading to all results being the same
Fix: Append a copy of the array (arr.copy()) when recording a permutation

Summary

Generates all possible orders of the array elements by swapping and backtracking.

Use when you need to explore every arrangement of a set of items.

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

Practice

1. What does the function permutations from Python's itertools module do when given an array as input?

easy

A. Generates all possible orderings of the elements in the array

B. Sorts the array in ascending order

C. Removes duplicate elements from the array

D. Returns the array reversed

Solution

1. Step 1: Understand the purpose of permutations

   The permutations function creates all possible ways to arrange the elements of the input array.

2. Step 2: Compare with other options

   Sorting, removing duplicates, or reversing are different operations and not what permutations does.

3. Final Answer:

   Generates all possible orderings of the elements in the array -> Option A

4. Quick Check:

   Permutations = all orderings [OK]

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

Common Mistakes:

• Confusing permutations with sorting
• Thinking permutations remove duplicates
• Assuming permutations reverse the array

2. Which of the following is the correct syntax to generate all permutations of the list [1, 2, 3] using itertools.permutations in Python?

easy

A. from itertools import permutation
perms = permutations([1, 2, 3])

B. from itertools import permutation
perms = permutation([1, 2, 3])

C. import itertools
perms = itertools.permutations([1, 2, 3])

D. import itertools
perms = itertools.permutation([1, 2, 3])

Solution

1. Step 1: Check correct import and function name

   The correct module is itertools and the function is permutations (plural).

2. Step 2: Verify syntax correctness

   import itertools perms = itertools.permutations([1, 2, 3]) correctly imports itertools and calls itertools.permutations with the list.

3. Final Answer:

   import itertools perms = itertools.permutations([1, 2, 3]) -> Option C

4. Quick Check:

   Correct import and function name = import itertools perms = itertools.permutations([1, 2, 3]) [OK]

Hint: Use plural 'permutations' and correct import [OK]

Common Mistakes:

• Using singular 'permutation' instead of 'permutations'
• Wrong import statement
• Calling function without module prefix when not imported directly

3. What is the output of the following code?

from itertools import permutations
for p in permutations([1, 2]):
    print(p)

medium

A. (1, 2)\n(2, 1)

B. [1, 2]\n[2, 1]

C. (1, 2)\n(1, 2)

D. [1, 2]\n[1, 2]

Solution

1. Step 1: Understand permutations output type

   itertools.permutations returns tuples representing each permutation.

2. Step 2: List all permutations of [1, 2]

   They are (1, 2) and (2, 1), printed on separate lines.

3. Final Answer:

   (1, 2)\n(2, 1) -> Option A

4. Quick Check:

   Permutations of two elements = two tuples [OK]

Hint: Permutations output tuples, not lists [OK]

Common Mistakes:

• Expecting lists instead of tuples
• Repeating same permutation twice
• Confusing output format with string or list

4. The following code is intended to print all permutations of [1, 2, 3]. What is the error?

from itertools import permutations
perms = permutations([1, 2, 3])
print(perms)

medium

A. The import statement is incorrect

B. It prints a permutations object, not the permutations themselves

C. The list should be converted to a tuple first

D. The function permutations does not exist

Solution

1. Step 1: Understand what permutations returns

   permutations returns an iterator object, not a list of permutations directly.

2. Step 2: Printing the iterator shows its object info, not permutations

   To see permutations, you must iterate or convert to list first.

3. Final Answer:

   It prints a permutations object, not the permutations themselves -> Option B

4. Quick Check:

   Printing iterator shows object info, not data [OK]

Hint: Convert iterator to list to see permutations [OK]

Common Mistakes:

• Expecting print to show permutations directly
• Thinking import is wrong
• Believing input must be tuple

5. You want to generate all permutations of the array [1, 2, 2] but only keep unique permutations (no duplicates). Which approach correctly achieves this in Python?

hard

A. Use list(permutations([1, 2, 2])) directly

B. Use permutations(set([1, 2, 2])) to generate permutations of unique elements

C. Sort the array first, then use permutations

D. Use set(permutations([1, 2, 2])) to remove duplicate tuples

Solution

1. Step 1: Understand duplicates in permutations

   Input has repeated elements, so permutations include duplicates.

2. Step 2: Remove duplicates by converting permutations to a set

   Using set() on permutations removes duplicate tuples, keeping unique permutations only.

3. Final Answer:

   Use set(permutations([1, 2, 2])) to remove duplicate tuples -> Option D

4. Quick Check:

   Set removes duplicates from permutations [OK]

Hint: Convert permutations to set to remove duplicates [OK]

Common Mistakes:

• Using set on input list before permutations (loses duplicates)
• Assuming sorting removes duplicates
• Not removing duplicates at all