Permutation and Combination in Python

Python provides direct methods to find permutations and combinations of a sequence. These methods are present in itertools package.

Permutation 

First import itertools package to implement the permutations method in python. This method takes a list as an input and returns an object list of tuples that contain all permutations in a list form. 
 

Output: 

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

Time complexity: O(n!), where n is the length of the input list. This is because there are n! permutations of n elements, and the program generates and prints all of them.
Auxiliary space: O(n!), as the program needs to store all n! permutations in memory before printing them out. Specifically, the perm variable created by calling permutations([1, 2, 3]) stores all n! permutations in memory as a list.

It generates n! permutations if the length of the input sequence is n. 
If want  to get permutations of length L then implement it in this way. 

Output: 

(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)

The time complexity of this program is O(n^r) where n is the length of the input array and r is the length of permutations to be generated. 

The space complexity is also O(n^r) as all permutations are stored in memory before printing.

It generates nCr * r! permutations if the length of the input sequence is n and the input parameter is r.

Combination 

This method takes a list and an input r as an input and return an object list of tuples which contain all possible combination of length r in a list form. 
 

Output: 

(1, 2)
(1, 3)
(2, 3)

1. Combinations are emitted in lexicographic sort order of input. So, if the input list is sorted, the combination tuples will be produced in sorted order. 
 

Output: 

(1, 2)
(1, 3)
(2, 3)

2. Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeat values in each combination. 
 

Output: 

(2, 1)
(2, 3)
(1, 3)

3. If we want to make a combination of the same element to the same element then we use combinations_with_replacement. 
 

Output:

(1, 1)
(1, 2)
(1, 3)
(2, 2)
(2, 3)
(3, 3)