Program to Compute all the Permutations of the String

Python Program to Compute all the Permutations of the String

Strings in Python:

A string is a group of alphabets, words, or other characters. It is a primitive data structure that serves as the foundation for data manipulation. Python has a string class called str. Strings in Python are “immutable,” which means they can’t be modified once they’re formed. Because of the immutability of strings, we generate new strings as we go to represent computed values.

Permutations:

The term “permutations” refers to the various ways in which elements can be organized. The elements may be strings, lists, or some other form of data. It is the rearranging of objects in various ways.

Given a string, the task is to print all the possible permutations of the given string in python.

Examples:

Example1:

Input:

string="cold"

Output:

Printing all permutations of the given string cold
cold
codl
clod
cldo
cdlo
cdol
ocld
ocdl
olcd
oldc
odlc
odcl
locd
lodc
lcod
lcdo
ldco
ldoc
dolc
docl
dloc
dlco
dclo
dcol

Example2:

Input:

string="win"

Output:

Printing all permutations of the given string win
win
wni
iwn
inw
niw
nwi

Program to Compute all the Permutations of the String in Python

Below are the ways to compute all the permutations of a string in python:

Grab the opportunity to learn all effective java programming language concepts from basic to advance levels by practicing these Java Program Examples with Output

Method #1:Using Recursion(Naïve Approach)

To solve this problem, we must first grasp the idea of Backtracking.

Solving this problem using Backtracking algorithm

Let us consider the given string is ‘ABC’.

The Backtracking algorithm :

  • Fix one of the characters in the first place and replace the rest of the characters with the first. In the first iteration, three strings are generated, as in ABC, by swapping A with A, B, and C, respectively.
  • Repeat step 1 for the remaining characters, such as fixing second character B, and so on.
  • Now go back to your previous place. For example, from ABC, we shaped ABC by fixing B again, then we returned to the previous position and swapped B with C. So we now have ABC and ACB.
  • To get all the permutations, repeat these steps for BAC and CBA.

Approach:

  • Scan the given string.
  • Fix one of the characters and swap the others.
  • For the remaining characters, use printPermutations() function.
  • Retrace your steps and swap the characters once more.

Below is the implementation:

# function which prints the permutations
def printPermutations(string, start, end):
    i = 0
    # printing the permutations
    if(start == end-1):
        print(string)
    else:
        for i in range(start, end):

           # Fixing a character and swapping the string
            samstring = list(string)
            # swapping using ,
            samstring[start], samstring[i] = samstring[i], samstring[start]
      # For the remaining characters, call printPermutations() recursively.

            printPermutations("".join(samstring), start+1, end)
            # Fixing a character and swapping the string
            # swapping using ,
            samstring[start], samstring[i] = samstring[i], samstring[start]


# given string
string = "cold"
# calculating the length of string
length = len(string)
print("Printing all permutations of the given string", string)
# passing string and 0th index as it is fixed at the starting
printPermutations(string, 0, length)

Output:

Printing all permutations of the given string cold
cold
codl
clod
cldo
cdlo
cdol
ocld
ocdl
olcd
oldc
odlc
odcl
locd
lodc
lcod
lcdo
ldco
ldoc
dolc
docl
dloc
dlco
dclo
dcol

Method #2:Using itertools permutations function

Using the permutations() function in Python, we may obtain permutations of elements in a list using the built-in module itertools.

We use join() function to join all the characters of the specific function and we store them into list using List Comprehension.

Below is the implementation:

# importing permutations from itertools
from itertools import permutations
# given string
string = "cold"
# Geeting all permutations as a list using comprehension
stringPermutations = [''.join(permutestr)
                      for permutestr in permutations(string)]
print("Printing all permutations of the given string", string)
# print all the permutations of the string
for i in stringPermutations:
    print(i)

Output:

Printing all permutations of the given string cold
cold
codl
clod
cldo
cdol
cdlo
ocld
ocdl
olcd
oldc
odcl
odlc
lcod
lcdo
locd
lodc
ldco
ldoc
dcol
dclo
docl
dolc
dlco
dloc

Related Programs: