Permutations

excerpt: Given an array of distinct integers, return all the possible permutations. You can return the answer in any order. tags: permutation backtracking exhaustive-enumeration

Given an array of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:
Input: nums = [1]
Output: [[1]]

Constraints

1 <= nums.length <= 6
-10 <= nums[i] <= 10

All the integers of nums are unique.

Using Flag

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def wrapper(nums, output, permutation, used)
  if permutation.size == nums.size
    output << permutation.dup

    return
  end
  
  for i in (0..nums.size-1)
    unless used[i]
      used[i] = true
      permutation << nums[i]
      wrapper(nums, output, permutation, used)
      permutation.pop
      used[i] = false
    end
  end
end

def permute(nums)
  output = []
  permutation = []
  used = Array.new(nums.size, false)


  wrapper(nums, output, permutation, used)
  output
end

Identify the invariants

The permutation must be unique
The numbers in the permutation must be unique
Every permutation is of the same size as the input
The number of n!

Solve this problem by hand to gain some insights. Think with pen and paper.
Constraints
Base Cases: array size: 1
- return that array in the output
Unit of work
- Make one choice from the given set of options
When the size of the intermediate result becomes equal to the size of the input. We push it to output array.

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

[2,3]
[3,2]

[1,3]

[1,3]
[3,1]

[1,2]
[1,2]
[2,1]

You identify a smaller, self similar problem.

[2,3]
[3,2]

[1,3]
[3,1]

[1,2]
[2,1]

Identify the self similarity

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

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

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

Permutations

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def wrapper(position, nums, output, permutation, used)
  if position == nums.size
    output << permutation.dup
    return
  end
  
  for i in (0..nums.size-1)
    unless used[i]
      used[i] = true 
      permutation[position] = nums[i]
      wrapper(position+1, nums, output, permutation, used)
      used[i] = false
    end
  end
end

def permute(nums)
  output = []
  permutation = []
  used = Array.new(nums.size, false)

  wrapper(0, nums, output, permutation, used)
  output
end

If you move the resetting used flag to false outside the unless condition, you will violate the invariant. The number of elements in the permutation will exceed 3.

Working Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# @param {Integer[]} nums
# @return {Integer[][]}

def permute_wrapper(nums, chosen)
  if nums.empty?
    p chosen
  end
  # for each choice
  for i in (0..nums.size-1)
    n = nums[i]
    # choose
    chosen << n
    nums.delete(n)
    # explore
    permute_wrapper(nums, chosen)
    # unchoose
    chosen.delete(n)
    nums.insert(i, n)
  end
end

def permute(nums)
  @output = []
  permute_wrapper(nums, [])
end

permute([1,2,3])

def wrapper(nums, chosen, output)
  if nums.empty?
    output << chosen.dup
  end
    
  for i in (0..nums.size-1)
    n = nums[i]
    chosen << n
    nums.delete(n)
    wrapper(nums, chosen, output)
    chosen.delete(n)
    nums.insert(i, n)
  end
end

# @param {Integer[]} nums
# @return {Integer[][]}
def permute(nums)
  output = []
  chosen = []
  wrapper(nums, chosen, output)
  output    
end

Refactored Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# @param {Integer[]} nums
# @return {Integer[][]}
def wrapper(nums, chosen, output)
  # If we hit the leaf node, we have one permutation, 
  # we can start backtracking
  if nums.empty?
    output << chosen.dup
  end
  
  for i in (0..nums.size-1)
    # Unit of work : choosing one number
    # Choose
    n = nums[i]
    chosen << n
    nums.delete(n)
    # Explore
    wrapper(nums, chosen, output)
    
    # Unchoose  
    chosen.delete(n)
    nums.insert(i, n)
  end
end

def permute(nums)
  output = []
  wrapper(nums, [], output)
  output
end

There are five different ways to solve this problem:

Swap
Choose/Explore/Unchoose
Fix the location and vary the numbers
Fix the number and vary the location
Letter combination

 0 1 2
[1,2,3]
[2,1,3]
[3,2,1]

What are the variables?
What are the indices?
What are the numbers?

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

Given: [1,2,3]

Generate:

 0 1 2
[1,2,3]
[1,3,2]
 
[2,1,3]
[2,3,1]
 
[3,1,2]
[3,2,1]

Analyze the Output

Avoid using any implementation details such as index or loops etc.

Pattern Recognition From the given output, what regularity do you observe? What is varying?
- The first item stays the same
- The other items are swapped What stays the same?
- Length of the nums
- We pick the location for the first item What is repeating?
- Keep the first item, you swap the other two There is a relationship between the number of permutations and the size of the input. n!. T: O(n!)
How to Generate? How do we swap if we have more than 3 items? The relationship between mathematical induction and recursion 0,1,2,3 …. n.
What is the base case? When do we have one of the permutations? When the length of the partial matches the length of the input.
We need to indicate that the child can use the available positions in the array. Using an auxiliary array with true/false to indicate with indices are available for the child to use.
Unit of Work
- What is the smallest unit of work that every recursive call needs to do? Check the level, first element, second element Process one element Put one of the element in one position We need to pick the element from the given array We need to tell the child which positions are available for its use
- Housekeeping work before making the recursive call We need to use an array with boolean values to indicate availability

3 * 2 * 1
4 * 3 * 2 * 1

Time and Space Complexity

Time: O(n!) Space: O(H)

Finding all possible permutations of a given array of distinct integers can be done using recursive backtracking.

Here’s a step-by-step guide:

Create a Function for Recursion: Create a helper function that takes the current permutation as a parameter.
Base Case: If the current permutation’s length is equal to the length of the given array, add it to the result list.
Recursion: For each element in the array, if it’s not already in the current permutation, add it and call the recursive function.
Backtrack: After the recursive call, remove the last element to try the next possibility.
Collect Results: Initiate the recursion from the main function and return the collected permutations.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(current):
            # Base case: if the current permutation's length is equal to nums' length, add to result
            if len(current) == len(nums):
                result.append(current[:]) # Make a copy of current permutation
                return

            # Iterate through nums and add each element if it's not already in the current permutation
            for num in nums:
                if num in current:
                    continue
                current.append(num)
                backtrack(current) # Recursive call
                current.pop() # Backtrack

        result = []
        backtrack([]) # Start recursion
        return result

Explanation:

The backtrack function is a recursive function that constructs permutations.
It iterates through the elements in nums, and for each element, it checks if it’s already in the current permutation. If not, it’s added, and the function calls itself recursively.
After exploring all possibilities for a given element, we remove it (backtrack) and try the next one.
When a complete permutation is constructed, it’s added to the result.

Since there are ( n! ) (n factorial) permutations for an array of size n, the time complexity of this code is ( O(n!) ).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# @param {Integer[]} nums
# @return {Integer[][]}
def wrapper(nums, chosen, output)
  # If we hit the leaf node, we have one permutation, 
  # we can start backtracking
  if nums.empty?
    output << chosen.dup
  end
  
  for i in (0..nums.size-1)
    # Unit of work : choosing one number
    # Choose
    n = nums[i]
    chosen << n
    nums.delete(n)
    # Explore
    wrapper(nums, chosen, output)
    
    # Unchoose  
    chosen.delete(n)
    nums.insert(i, n)
  end
end

def permute(nums)
  output = []
  wrapper(nums, [], output)
  output
end

Swap
Choose/Explore/Unchoose
Fix the location and vary the numbers
Fix the number and vary the location
Letter combination

0 1 2 [1,2,3] [2,1,3] [3,2,1]

What are the variables? What are the indices? What are the numbers?

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

Given: [1,2,3]

Generate:

0 1 2 [1,2,3] [1,3,2]

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

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

Analyze the Output

Avoid using any implementation details such as index or loops etc.

Pattern Recognition From the given output, what regularity do you observe?
What is varying?
- The first item stays the same
- The other items are swapped
What stays the same?
- Length of the nums
- We pick the location for the first item
What is repeating?
- Keep the first item, you swap the other two

There is a relationship between the number of permutations and the size of the input. n!. T: O(n!)

How to Generate How do we swap if we have more than 3 items? The relationship between mathematical induction and recursion 0,1,2,3 …. n
What is the base case? When do we have one of the permutation? When the length of the partial matches the length of the input.
We need to indicate that the child can use the available positions in the array. Using an auxiliary array with true/false to indicate with indices are available for the child to use.
Unit of Work
- What is the smallest unit of work that every recursive call need to do? Check the level, first element, second element Process one element Put one of the element in one position
We need to pick the element from the given array We need to tell the child which positions are available for its use
- Housekeeping work before making the recursive call We need to use an array with boolean values to indicate availability

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def wrapper(nums, output, permutation, used)
   if permutation.size == nums.size  
     output << permutation.dup
       return
   end

    for i in (0..nums.size-1)
       if !used[i] 
           used[i] = true
           permutation << nums[i]
           wrapper(nums, output, permutation, used)
           permutation.pop
           used[i] = false
       end

    end
        
end

# @param {Integer[]} nums
# @return {Integer[][]}
def permute(nums)
    output = []
    permutation = []
    used = Array.new(nums.size, false)
    
    wrapper(nums, output, permutation, used)
    
    return output
end

title: Permutations excerpt: This covers the choose-explore-unchoose steps in backtracking. tags: choose-explore-unchoose backtracking using-flag-to-exclude-element

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique

There are five different ways to solve this problem:

Swap
Choose/Explore/Unchoose
Fix the location and vary the numbers
Fix the number and vary the location
Letter combination

0 1 2 [1,2,3] [2,1,3] [3,2,1]

What are the variables?
What are the indices?
What are the numbers?

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

Given: [1,2,3] Generate: 0 1 2 [1,2,3] [1,3,2]

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

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

Analyze the Output

Pattern Recognition

From the given output, what regularity do you observe?

What is varying?

The first item stays the same
The other items are swapped

What stays the same?

Length of the nums
We pick the location for the first item

What is repeating?

Keep the first item, you swap the other two. There is a relationship between the number of permutations and the size of the input. n!. T: O(n!)

How to Generate

How do we swap if we have more than 3 items?

The relationship between mathematical induction and recursion. 0,1,2,3 …. n

What is the base case?

When do we have one of the permutations?

When the length of the partial matches the length of the input. We need to indicate that the child can use the available positions in the array. Using an auxiliary array with true/false to indicate with indices are available for the child to use.

Unit of Work

What is the smallest unit of work that every recursive call needs to do?
- Check the level, first element, second element
- Process one element
- Put one of the element in one position
We need to pick the element from the given array
We need to tell the child which positions are available for its use
Housekeeping work before making the recursive call. We need to use an array with boolean values to indicate availability

3 * 2 * 1 4 * 3 * 2 * 1

Time: O(n!) Space: O(H)

Flag Approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def wrapper(nums, output, permutation, used)
  if permutation.size == nums.size
    output << permutation.dup

    return
  end
  
  for i in (0..nums.size-1)
    unless used[i]
      used[i] = true
      permutation << nums[i]
      wrapper(nums, output, permutation, used)
      permutation.pop
      used[i] = false
    end
  end
end

def permute(nums)
  output = []
  permutation = []
  used = Array.new(nums.size, false)

  wrapper(nums, output, permutation, used)
  output
end

If you move the resetting used flag to false outside the unless condition, you will violate the invariant. The number of elements in the permutation will exceed 3.

Identify the invariants

The permutation must be unique
The numbers in the permutation must be unique
Every permutation is of the same size as the input
The number of generated sequence is equal to n!

Solve this problem by hand to gain some insights. Think with pen and paper.

Base Cases

Array size: 1

return that array in the output

Unit of work

Make one choice from the given set of options

When the size of the intermediate result becomes equal to the size of the input, we push it to output array.

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

[2,3] [3,2]

[1,3]

[1,3] [3,1]

[1,2] [1,2] [2,1]

You identify a smaller, self similar problem.

[2,3] [3,2]

[1,3] [3,1]

[1,2] [2,1]

Identify the self similarity

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def wrapper(nums, chosen, output)
  if nums.empty?
    output << chosen.dup
  end
    
  for i in (0..nums.size-1)
    n = nums[i]
    chosen << n
    nums.delete(n)
    wrapper(nums, chosen, output)
    chosen.delete(n)
    nums.insert(i, n)
  end
end

# @param {Integer[]} nums
# @return {Integer[][]}
def permute(nums)
  output = []
  chosen = []
  wrapper(nums, chosen, output)
  output    
end

Refactored Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# @param {Integer[]} nums
# @return {Integer[][]}
def wrapper(nums, chosen, output)
  # If we hit the leaf node, we have one permutation, 
  # we can start backtracking
  if nums.empty?
    output << chosen.dup
  end
  
  for i in (0..nums.size-1)
    # Unit of work : choosing one number
    # Choose
    n = nums[i]
    chosen << n
    nums.delete(n)
    # Explore
    wrapper(nums, chosen, output)

    # Unchoose  
    chosen.delete(n)
    nums.insert(i, n)
  end
end

def permute(nums)
  output = []
  wrapper(nums, [], output)
  output
end

title: Generating Permutations excerpt: This covers generating permutations with duplicates and without duplicates. tags: include-exclude using-flags-to-exclude

Generating permutations is very similar to generating combinations.

Permutations with Duplicates

The code for generating permutations with duplicates:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def permutation(array, index, result, output)
  # Check if we have generated the last permutation
  if index == array.size
    # Save the result in the output
    for i in (0..result.size)
      output.append(array[result[i]])
    end
  else
    # Generate the next permutation
    for i in (0..array.size - 1)
      # Add item i to the result
      result[index] = i
      
      # Recursively generate the other permutations
      permutation(array, index + 1, result, output)
    end
  end
end

The main difference between this method and generating combinations with duplicates is that this method loops through all the items when it makes its assignment instead of starting the loop at a start value. So we can pick items in any order, generating all the permutations.

Permutations Without Duplicates

Permutations without duplicates can be generated by making only minor change to the code in the previous section. Items that have already been used must be excluded.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def permutation(array, index, result, output)
  # Check if we have generated the last permutation
  if index == array.size
    # Save the result in the output
    for i in (0..result.size)
      output.append(array[result[i]])
    end
  else
    # Generate the next permutation
    for i in (0..array.size - 1)
      # Make sure item i has not been used yet
      used = false
      for j in (0..index - 1)
        if result[j] == i
          used = true
        end
      end

      if !used 
        # Add item i to the result
        result[index] = i

        # Recursively generate the other permutations
        permutation(array, index + 1, result, output)
      end      
    end
  end
end

The only modification in this program is that item that has been used is excluded from the permutation.

Generating Bit Strings

Bit strings can be generated and it can be used when an array consists of either integers or characters. After generating the bit strings, we loop through the given array of integers or characters and output the permutations.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def bit_strings(index, array, result)
  # Base case
  if index == array.length
    result << array.dup
  else
    # Make a choice to include
    array[index] = 1
    bit_strings(index+1, array, result)
    # Make a choice to exclude
    array[index] = 0
    bit_strings(index+1, array, result)
  end
end

index = 0
array = [0,0,0]
result = []

bit_strings(index, array, result)
p result