Learn about Permutations in Python. Show
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. 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 LibraryWe 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:
1. Permutations of a String using RecursionBefore 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:
EXAMPLE:
Output: 2. Permutations of a String using itertoolsWe 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:
EXAMPLE: To print the permutations as words, we can join the tuples as in the below code:
Output: Explanation:
Permutations of NumbersSimilar 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 LengthSuppose 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 itertoolsSYNTAX: 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:
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:
Combinations of NumbersSimilar 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 NumbersWhat 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 ReplacementLet 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. Conclusion
How do you write permutations of a string in Python?Find all permutations of a string in Python. import itertools.. if __name__ == '__main__':. s = 'ABC'. nums = list(s). permutations = list(itertools. permutations(nums)). # Output: ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']. print([''. join(permutation) for permutation in permutations]). How do you calculate permutations and combinations in Python?To calculate combinations in Python, use the itertools. combinations() method. The itertools. combinations() method takes an iterator as an argument and returns all the possible combinations of elements in the iterator.
What is Permute in Python?A permutation, also called an “arrangement number” or “order”, is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation. Examples: Input : str = 'ABC' Output : ABC ACB BAC BCA CAB CBA.
How do you find the combination of a string?substring(1); Set<String> qq=find(st); for(String str:qq) { for(int i=0;i<=str. length();i++) { ss. add(comb(str,c,i)); } } } return ss; } public static String comb(String s,char c,int i) { String start=s. substring(0,i); String end=s.
|