How do you generate a permutation of a string in python?

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 
         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!) 

View Discussion

Improve Article

Save Article

View Discussion

Improve Article

Save Article

Given a string, write a Python program to find out all possible permutations of a string. Let’s discuss a few methods to solve the problem.
Method #1: Using Naive Method 
 

Python3

ini_str = "abc"

print("Initial string", ini_str)

result = []

def permute(data, i, length):

    if i == length:

        result.append(''.join(data) )

    else:

        for j in range(i, length):

            data[i], data[j] = data[j], data[i]

            permute(data, i + 1, length)

            data[i], data[j] = data[j], data[i] 

permute(list(ini_str), 0, len(ini_str))

print("Resultant permutations", str(result))

Output:

Initial string abc
Resultant permutations ['abc', 'acb', 'bac', 'bca', 'cba', 'cab']

  
Method #2: Using itertools 
 

Python3

from itertools import permutations

ini_str = "abc"

print("Initial string", ini_str)

permutation = [''.join(p) for p in permutations(ini_str)]

print("Resultant List", str(permutation))

Output:

Initial string abc
Resultant List ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']