Generate All Permutations of Array in DSA Python - Execution Trace

Concept Flow - Generate All Permutations of Array

Start with full array

↓

Choose element at index i

↓

Swap element i with element j

↓

Recurse with i+1

↓

If i == length, record permutation

↓

Backtrack: swap back elements i and j

↩Back to choose next j

We pick each element in turn, swap it to the current position, recurse to fix the next position, record when done, then swap back to restore.

Execution Sample

DSA Python

def permute(arr, start=0):
    if start == len(arr):
        print(arr)
        return
    for i in range(start, len(arr)):
        arr[start], arr[i] = arr[i], arr[start]
        permute(arr, start+1)
        arr[start], arr[i] = arr[i], arr[start]

This code generates all permutations by swapping elements starting from index 'start' and recursing.

Execution Table

Step	Operation	Current Index (start)	Swapped Indices	Array State	Action
1	Start permute	0	None	[1, 2, 3]	Begin with full array
2	Swap	0	(0,0)	[1, 2, 3]	Swap element 0 with 0 (no change)
3	Recurse	1	None	[1, 2, 3]	Recurse with start=1
4	Swap	1	(1,1)	[1, 2, 3]	Swap element 1 with 1 (no change)
5	Recurse	2	None	[1, 2, 3]	Recurse with start=2
6	Swap	2	(2,2)	[1, 2, 3]	Swap element 2 with 2 (no change)
7	Recurse	3	None	[1, 2, 3]	start == len(arr), record permutation: [1, 2, 3]
8	Backtrack	2	(2,2)	[1, 2, 3]	Swap back elements 2 and 2
9	Backtrack	1	(1,1)	[1, 2, 3]	Swap back elements 1 and 1
10	Swap	1	(1,2)	[1, 3, 2]	Swap element 1 with 2
11	Recurse	2	None	[1, 3, 2]	Recurse with start=2
12	Swap	2	(2,2)	[1, 3, 2]	Swap element 2 with 2 (no change)
13	Recurse	3	None	[1, 3, 2]	start == len(arr), record permutation: [1, 3, 2]
14	Backtrack	2	(2,2)	[1, 3, 2]	Swap back elements 2 and 2
15	Backtrack	1	(1,2)	[1, 2, 3]	Swap back elements 2 and 1
16	Backtrack	0	(0,0)	[1, 2, 3]	Swap back elements 0 and 0
17	Swap	0	(0,1)	[2, 1, 3]	Swap element 0 with 1
18	Recurse	1	None	[2, 1, 3]	Recurse with start=1
19	Swap	1	(1,1)	[2, 1, 3]	Swap element 1 with 1 (no change)
20	Recurse	2	None	[2, 1, 3]	Recurse with start=2
21	Swap	2	(2,2)	[2, 1, 3]	Swap element 2 with 2 (no change)
22	Recurse	3	None	[2, 1, 3]	start == len(arr), record permutation: [2, 1, 3]
23	Backtrack	2	(2,2)	[2, 1, 3]	Swap back elements 2 and 2
24	Backtrack	1	(1,1)	[2, 1, 3]	Swap back elements 1 and 1
25	Swap	1	(1,2)	[2, 3, 1]	Swap element 1 with 2
26	Recurse	2	None	[2, 3, 1]	Recurse with start=2
27	Swap	2	(2,2)	[2, 3, 1]	Swap element 2 with 2 (no change)
28	Recurse	3	None	[2, 3, 1]	start == len(arr), record permutation: [2, 3, 1]
29	Backtrack	2	(2,2)	[2, 3, 1]	Swap back elements 2 and 2
30	Backtrack	1	(1,2)	[2, 1, 3]	Swap back elements 2 and 1
31	Backtrack	0	(0,1)	[1, 2, 3]	Swap back elements 1 and 0
32	Swap	0	(0,2)	[3, 2, 1]	Swap element 0 with 2
33	Recurse	1	None	[3, 2, 1]	Recurse with start=1
34	Swap	1	(1,1)	[3, 2, 1]	Swap element 1 with 1 (no change)
35	Recurse	2	None	[3, 2, 1]	Recurse with start=2
36	Swap	2	(2,2)	[3, 2, 1]	Swap element 2 with 2 (no change)
37	Recurse	3	None	[3, 2, 1]	start == len(arr), record permutation: [3, 2, 1]
38	Backtrack	2	(2,2)	[3, 2, 1]	Swap back elements 2 and 2
39	Backtrack	1	(1,1)	[3, 2, 1]	Swap back elements 1 and 1
40	Swap	1	(1,2)	[3, 1, 2]	Swap element 1 with 2
41	Recurse	2	None	[3, 1, 2]	Recurse with start=2
42	Swap	2	(2,2)	[3, 1, 2]	Swap element 2 with 2 (no change)
43	Recurse	3	None	[3, 1, 2]	start == len(arr), record permutation: [3, 1, 2]
44	Backtrack	2	(2,2)	[3, 1, 2]	Swap back elements 2 and 2
45	Backtrack	1	(1,2)	[3, 2, 1]	Swap back elements 2 and 1
46	Backtrack	0	(0,2)	[1, 2, 3]	Swap back elements 2 and 0
47	End	None	None	[1, 2, 3]	All permutations generated, stop

💡 All indices swapped and recursed, start reached array length, permutations recorded.

Variable Tracker

Variable	Start	After Step 2	After Step 10	After Step 17	After Step 32	Final
arr	[1, 2, 3]	[1, 2, 3]	[1, 3, 2]	[2, 1, 3]	[3, 2, 1]	[1, 2, 3]
start	0	0	1	0	0	None
i (swap index)	None	0	2	1	2	None

Key Moments - 3 Insights

Why do we swap elements back after recursion?

Swapping back restores the array to its original state before the next iteration, as shown in steps 8, 14, 15, 29, 30, 31, 38, 39, 44, 45, 46. Without this, later permutations would be incorrect.

Why do we record the permutation only when start == len(arr)?

When start equals the array length (step 7, 13, 22, 28, 37, 43), it means all positions are fixed and a complete permutation is formed, so we record it.

Why do we swap element at 'start' with elements at indices from 'start' to end?

Swapping with indices from 'start' to end (steps 2, 10, 17, 25, 32, 40) ensures we explore all possible elements in the current position, generating all permutations.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after step 10?

A [1, 3, 2]

B [1, 2, 3]

C [2, 1, 3]

D [3, 2, 1]

💡 Hint

Check the 'Array State' column in row with Step 10.

At which step does the first complete permutation get recorded?

A Step 22

B Step 13

C Step 7

D Step 37

💡 Hint

Look for 'record permutation' in the 'Action' column in the execution table.

If we skip swapping back after recursion, what happens to the array state at step 15?

A [1, 2, 3]

B [1, 3, 2]

C [2, 1, 3]

D [3, 2, 1]

💡 Hint

Step 15 shows swap back restoring the array to [1, 2, 3]; without it, the array remains swapped as in step 10.

Concept Snapshot

Generate All Permutations of Array:
- Use recursion with a 'start' index.
- Swap elements at 'start' with each index from 'start' to end.
- Recurse with start+1.
- When start == length, record permutation.
- Swap back after recursion to restore array.
- This explores all possible orderings.

Full Transcript

This visualization shows how to generate all permutations of an array by swapping elements starting from a 'start' index. At each step, we swap the element at 'start' with each element from 'start' to the end, then recurse to fix the next position. When 'start' reaches the array length, a complete permutation is recorded. After recursion, we swap back to restore the array for the next iteration. The execution table traces each swap, recursion, and backtrack step, showing the array state and actions. Key moments clarify why swapping back is necessary, why permutations are recorded only at the end, and why we swap with all indices from 'start' onward. The quiz tests understanding of array states and recording steps. This method ensures all permutations are generated without duplicates or missing any.

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