String permutations program in python

Question

In this example, you will learn to compute all the permutation of the string.

Nội dung chính Show

Example 1: Using recursion
Example 2: Using itertools
How do you print 3 permutations in Python?
How do you do permutations in Python without Itertools?
What is permutations of list in Python?
How do you find the permutations of an element in a list Python?

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
None

In 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

Read

Discuss

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 
         CBA

We 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
CBA

Permutation 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
KEEG

Time Complexity: O(n!) where n is the size of the string.
Auxiliary Space: O(n!)

How do you print 3 permutations in Python?

python create a program that runs through all possible combinations.

from itertools import combinations..

lst = ["a" ,"b", "c"].

lengthOfStrings = 3..

for i in combinations(lst, lengthOfStrings):.

print(i).

How do you do permutations in Python without Itertools?

A. To create combinations without using itertools, iterate the list one by one and fix the first element of the list and make combinations with the remaining list. Similarly, iterate with all the list elements one by one by recursion of the remaining list.

What is permutations of list in Python?

Arranging all the members of a set into some order or sequence and if the set is already ordered, rearranging (reordering) its elements is called permutation.