In this example, you will learn to compute all the permutation of the string.
To understand this example, you should have the knowledge of the following Python programming topics:
- Python Strings
- Python for Loop
Permutation is the method of selecting elements from a set in different ways.
For example: the number of ways in which characters from yup can be selected are yup, ypu, uyp, upy, puy, pyu, and not selecting any.
We will perform the same in the following examples.
Example 1: Using recursion
def get_permutation(string, i=0): if i == len(string): print("".join(string)) for j in range(i, len(string)): words = [c for c in string] # swap words[i], words[j] = words[j], words[i] get_permutation(words, i + 1) print(get_permutation('yup'))Output
yup ypu uyp upy puy pyu NoneIn this example, recursion is used to find the permutations of a string yup.
- The if condition prints string passed as argument if it is equal to the length of yub.
- In each iteration of the for loop, each character of yup is stored in words.
- The elements of words are swapped. In this way, we achieve all different combinations of characters.
- This process continues until the maximum length is reached.
Example 2: Using itertools
from itertools import permutations words = [''.join(p) for p in permutations('pro')] print(words)Output
['pro', 'por', 'rpo', 'rop', 'opr', 'orp']Using permutations from itertools module, we can find the permutations of a string.
why do you not simple do:
from itertools import permutations perms = [''.join(p) for p in permutations(['s','t','a','c','k'])] print perms print len(perms) print len(set(perms))you get no duplicate as you can see :
['stack', 'stakc', 'stcak', 'stcka', 'stkac', 'stkca', 'satck', 'satkc', 'sactk', 'sackt', 'saktc', 'sakct', 'sctak', 'sctka', 'scatk', 'scakt', 'sckta', 'sckat', 'sktac', 'sktca', 'skatc', 'skact', 'skcta', 'skcat', 'tsack', 'tsakc', 'tscak', 'tscka', 'tskac', 'tskca', 'tasck', 'taskc', 'tacsk', 'tacks', 'taksc', 'takcs', 'tcsak', 'tcska', 'tcask', 'tcaks', 'tcksa', 'tckas', 'tksac', 'tksca', 'tkasc', 'tkacs', 'tkcsa', 'tkcas', 'astck', 'astkc', 'asctk', 'asckt', 'asktc', 'askct', 'atsck', 'atskc', 'atcsk', 'atcks', 'atksc', 'atkcs', 'acstk', 'acskt', 'actsk', 'actks', 'ackst', 'ackts', 'akstc', 'aksct', 'aktsc', 'aktcs', 'akcst', 'akcts', 'cstak', 'cstka', 'csatk', 'csakt', 'cskta', 'cskat', 'ctsak', 'ctska', 'ctask', 'ctaks', 'ctksa', 'ctkas', 'castk', 'caskt', 'catsk', 'catks', 'cakst', 'cakts', 'cksta', 'cksat', 'cktsa', 'cktas', 'ckast', 'ckats', 'kstac', 'kstca', 'ksatc', 'ksact', 'kscta', 'kscat', 'ktsac', 'ktsca', 'ktasc', 'ktacs', 'ktcsa', 'ktcas', 'kastc', 'kasct', 'katsc', 'katcs', 'kacst', 'kacts', 'kcsta', 'kcsat', 'kctsa', 'kctas', 'kcast', 'kcats'] 120 120 [Finished in 0.3s]View Discussion
Improve Article
Save Article
View Discussion
Improve Article
Save Article
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 CBAWe have existing solution for this problem please refer Permutations of a given string using STL link. We can also solve this problem in python using inbuilt function permutations(iterable).
Python3
from itertools import permutations
def allPermutations(str):
permList = permutations(str)
for perm in list(permList):
print (''.join(perm))
if __name__ == "__main__":
str = 'ABC'
allPermutations(str)
Output:
ABC ACB BAC BCA CAB CBAPermutation and Combination in Python Permutations of a given string with repeating characters The idea is to use dictionary to avoid printing duplicates.
Python3
from itertools import permutations
import string
s = "GEEK"
a = string.ascii_letters
p = permutations(s)
d = []
for i in list(p):
if (i not in d):
d.append(i)
print(''.join(i))
Output:
GEEK GEKE GKEE EGEK EGKE EEGK EEKG EKGE EKEG KGEE KEGE KEEGTime Complexity: O(n!) where n is the size of the string.
Auxiliary Space: O(n!)