46. Permutations

Medium

$$_nP_r=\frac{n!}{(n-r)!}$$

Problem:

Given distinct integers, return all the possible permutations.

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

https://leetcode.com/problems/permutations

What to learn:

Copying Objects in Python

One of the key features of Python is that everything is an object. Unless you explicitly copy a value, every act of assigning a value to a variable results in a reference to the value object. In other words, if you modify the original value that the reference points to, all references, i.e., the values of all variables, are also changed accordingly.

So, how can we copy the value itself to prevent it from being a reference? The simplest method is using [:]. A more intuitive approach is to use the copy() method explicitly. Lastly, for nested lists that are more complex, you should handle them with deepcopy().

>>> a = [1, 2, 3]
>>> b = a
>>> c = a[:]
>>> id(a), id(b), id(c)
(4362781552, 4362781552, 4361580048)

>> d = a.copy()
>>> id(a), id(d)
(4362781552, 4363974768)

>>> import copy
>>> a = [1, 2, [3, 5], 4]
>>> b = copy.deepcopy(a)
>>> id(a), id(b), b
(4480589512, 4481610824, [1, 2, [3, 5], 4])

map()

map() function returns a map object(which is an iterator) of the results after applying the given function to each item of a given iterable (list, tuple etc.) Syntax :

map(fun, iter)

Parameters :

fun : It is a function to which map passes each element of given iterable. iter : It is a iterable which is to be mapped.

You can pass one or more iterable to the map() function. It will return a list of the results after applying the given function.

Returns:

The returned value from map() (map object) then can be passed to functions like list() (to create a list), set() (to create a set) .

# List of strings
l = ['sat', 'bat', 'cat', 'mat']
 
# map() can listify the list of strings individually
test = list(map(list, l))

print(test)
# [['s', 'a', 't'], ['b', 'a', 't'], ['c', 'a', 't'], ['m', 'a', 't']]

Reference: https://www.geeksforgeeks.org/python-map-function

Solution:

Backtracking

1. cur[:]

This is a way to create a shallow copy of the list cur. When you do cur[:], it creates a new list that contains all the elements of cur. This is important because if you just did result.append(cur), you would be appending a reference to the cur list, not a new list. This means that any changes you make to cur later on would also be reflected in the lists you've already appended to result, which is not what you want.

By using cur[:], you're ensuring that the list you append to result is a separate list that won't be affected by future changes to cur.

2. cur.pop():

The pop() method removes the last item from a list. In the context of backtracking, it's used to undo a choice, so you can explore other choices.

Here's a step-by-step breakdown of how it works in the code:

• You start with an empty cur list.

• You choose a number from nums and append it to cur.

• You recursively call backtrack to explore permutations with that choice.

• Once you've explored all permutations with that choice, you want to "undo" or "backtrack" that choice to explore other possibilities. This is where cur.pop() comes in. It removes the last choice (i.e., the last number you appended to cur), allowing you to try a different number in the next iteration of the loop.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []

        def backtrack(cur):
            if len(cur) == len(nums):
                result.append(cur[:]) # Make a copy of cur before appending
                return

            for num in nums:
                if num not in cur:
                    cur.append(num)
                    backtrack(cur)
                    cur.pop()  # Remove the last appended number to backtrack

        if nums:
            backtrack([])

        return result

The combination of appending a choice and then popping it off is a common pattern in backtracking algorithms. It allows you to explore all possible combinations without having to create a bunch of new lists or keep track of a lot of state.

itertools Module

The permutations() function returns a collection of tuples.

• itertools.permutations(nums): <itertools.permutations object at 0x7f175a735490>

• map(list,itertools.permutations(nums)): <map object at 0x7fa2a6046170>

• list(itertools.permutations(nums)): [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

• list(map(list, itertools.permutations(nums))): [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

import itertools

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(map(list, itertools.permutations(nums)))