Permutations in Python
FREE
Abstract
Permutations refer to the different ways in which we can arrange a given list of elements. Combinations are the ways in which we can select a certain subset of items from a bigger list, irrespective of the order of selection.
We can find the permutations and the combinations of a word or a set of numbers using recursion as well as pre-defined methods in the Python library itertools.
Introduction to Permutations in Python
Let's play a game :smiley: Try to form as many words as you can by using all the letters: O, T, P. (Hint: There are 3 words) Well, I am able to guess only two: POT and TOP :disappointed: How to find out the third?
We can use brute force to arrange the letters in the word OTP in all possible positions. We can find all the words using the different arrangements of the four letters. This is what we call as permutation.
Permutation refers to the different ways in which a given set of objects can be arranged. For example, in our problem, we can arrange the three letters in the following 6 ways.
We can find the different words which can be created from the set of three letters {O, T, P} using permutation and filter out the words which have a meaning. This gives us our 3 words: OPT, TOP and POT.
Now I want to play the game in teams of 3 and need to select 2 of my 4 friends to form my team. Remember that the order in which I pick them doesn't make any difference. This is known as combination. Combination is the way of selecting k items out of a collection of n items (k <= n), where the order of selection does not matter. The below diagram represents the 6 ways in which I can select 2 out of 4 friends.
The 6 ways or combinations from a set of four friends a, b, c and d are: (a, b), (a, c), (a, d), (b, c) (b, d), (c, d). Now that we have understood the significance of permutations and combinations, let us implement them using Python!
Importing the Required Library
We have specific methods in Python's itertools library to find the permutations and combinations for a given set of objects. To use them, we first import the itertools library as follows:
Let us see how we can use the predefined methods for calculating the permutations and combinations of a set of objects, in the subsequent sections.
What is Permutations in Python?
Let us take an example of the word formation game we discussed in the Introduction. How can we use Python to generate the permutations of the letters O, T, P
There are two ways of generating permutations in Python:
- Using recursion
- Using itertools
1. Permutations of a String using Recursion
Before we learn about the predefined method in itertools library, let us first look behind the scenes. We will find the permutations of a given string from scratch, using recursion.
Steps:
- We first define the base condition for recursion: If i is equal to the string's length, we join the array of letters and print the word.
- In the *findPermutations()* method, we swap the position of i-th and j-th letters in the word and pass it again to the function.
- This process is repeated until the maximum length of the word is reached. Each word is stored as a permutation of the original string.
EXAMPLE:
Output:
2. Permutations of a String using itertools
We use the predefined permutations() method in the itertools library to get all the permutations of a given set of objects.
SYNTAX:
permutations('OTP')
If we print the above command, we get the object location of the itertools object as follows:
<itertools.permutations object at 0x7f6e8c537f90>
To get all the permutations of the word OTP, we need to iterate through it using a for-loop. Each distinct permutation is returned in the form of a tuple.
PARAMETERS:
The permutations() method takes 2 parameters:
- Object - The object whose permutations we have to find
- Length (optional) - The desired length of each permutation. It takes the default value of the object length.
EXAMPLE:
To print the permutations as words, we can join the tuples as in the below code:
Output:
Explanation:
- In line 1, we import the permutations() method from itertools library.
- We pass the string 'OTP' as an input to the method. The various permutations are stored as a list of tuples in perm.
- In lines 4-5, we iterate through the list of tuples and print each permutation by joining the tuple of characters.
Permutations of Numbers
Similar to finding the permutations of a string, we can also find the permutations of a given set of numbers by passing them as an iterable. We use the same permutations() method and pass the list of numbers as a parameter.
EXAMPLE:
Output:
Explanation:
The above code is similar to finding permutations of a word. The only difference is in the way we pass the input - as a list of numbers. The permutations() method returns the different possible arrangements in the form of tuples.
Permutations of a Fixed Length
Suppose we now need to find all the two-letter words which can be formed using our initial string 'OTP'. It's time to use the optional length parameter of the permutations() method. We can specify the desired length of each permutation by passing it to our method.
EXAMPLE:
Output:
Explanation:
We pass the desired length of the permutation (here, 2) as the second parameter of the permutations() method. This prints all the possible arrangements of the word 'OTP' having a length of 2. We can similarly specify the length as the second parameter to get all permutations of a list of numbers as well.
What is Combinations in Python?
Combinations are the ways in which we can select k items from a list of n items, irrespective of the order of selection. Let us consider the problem where we needed to select 2 out of 4 friends to form our team. How can we generate all combinations of 2 friends from our group of friends (a, b, c, d)? We can use the predefined combinations() method of the itertools library to generate all possible combinations without repetition of items.
1. Combinations of Strings using itertools
SYNTAX:
combinations(['a', 'b', 'c', 'd'], 2)
If we print the above command, we get the object location of the itertools object as follows:
<itertools.combinations object at 0x7ff1aa80f090>
PARAMETERS:
The combinations() method takes 2 mandatory parameters:
- Object - The object whose combinations we have to find
- Length - The desired length of each combination. The number of items (k) we need to select from a list of n objects.
EXAMPLE:
To get all the combinations of 2 friends from our list of friends ['a', 'b', 'c', 'd'], we need to iterate through the combinations() method using a for-loop. The output will be a list of tuples, where each tuple is a unique combination. Below is how the code and output will look like:
Output:
Explanation:
- Line 1 imports the combinations() method from itertools library.
- In line 4, we pass two parameters to the method:
- The list friends for which we want the combinations
- Desired length of each combination (here, 2)
- In lines 6-7, we iterate through the different combinations stored as tuples and print them.
Combinations of Numbers
Similar to finding the combinations of a list of strings, we can also find the combinations of a given set of numbers. We use the same combinations() method and pass the list of numbers as a parameter.
EXAMPLE:
Output:
Explanation:
The above code is similar to finding combinations of a word or a list of strings. We pass the list of numbers and the desired length to the combinations() method. It then returns the different possible combinations in the form of tuples.
Combinations of Repeated Numbers
What if there are duplicates in the list for which we want the combinations? If there are multiple occurrences of a value in the input list, it will generate the same combination more than once. This is because the combinations are generated based on the indices or positions, not on the actual values. If there was no repetition, we would get all unique combinations, unlike in this case.
EXAMPLE:
Output:
Explanation:
In the above code, we have passed a numeric list with numbers 1 and 4 repeated twice. This is why some of the combinations like (1,4), (1,9), (4,1) and (4,9) are generated more than once.
Combinations with Replacement
Let us now look at a scenario where we want to allow the combination of an element with itself. This means that the individual elements can be repeated more than once, even if there's no repetition in the original input iterable. We use the combinations_with_replacement() method present within the itertools library to achieve this.
EXAMPLE:
Output:
Explanation:
When we compare this output to the one we got using the combinations() method, we find three extra results: (1,1), (4,4), (9,9). This is because when we pick an element from the list, the method combinations_with_replacement() replaces it with the same value to get combinations with itself.
Also,Click here to know more about Join() function in Python.
Conclusion
- Permutations refer to the ways in which we can arrange a set of objects.
- Combinations are the ways in which we can select k items from a list of n items, irrespective of the order of selection.
- The itertools library in Python has predefined methods for generating permutations and combinations for a set of objects.
- The permutations() method generates all permutations of a given set of objects and takes 2 parameters: Object and Length, where Length is optional.
- We can specify the desired length of permutations by specifying the length parameter.
- The combinations() method generates all combinations of a given set of objects and takes 2 parameters: Object and Length.
- Both the permutations() and combinations() method generate the result in the form of a list of tuples, where each tuple is a unique permutation or combination.
- The combinations_with_replacement() method allows the combination of an element with itself.