String Permutation in Python without itertools

Problem statement: Write a program to find all the permutations of the string in Python without itertools.

What is permutation?

A permutation is a technique that is used to determine all the strings obtained by rearranging the characters.

Example:

• The permutations of string “ab” is [‘ab’, ‘ba’].
• The permutations of string “abc” is [‘abc’, ‘acb’, ‘bac’, ‘bca’, ‘cba’, ‘cab’].

The number permutation that can be formed from the string is n! (n factorial). Where, n is the length of the given string.

Solution:

Here we are using recursion to get all the permutations of the string in Python.

Finding permutations in Python programming is very much easy using itertools Python module. But in competitive coding programming or coding interview, you have to use your own logic instead of using itertools.

Python code:

out=[]

def permute(msg, i, length):
    if i==length:
        out.append("".join(msg))
    else:
        for j in range(i, length):
            msg[i], msg[j] = msg[j], msg[i]
            permute(msg, i+1, length)
            msg[j], msg[i] = msg[i], msg[j]

msg="abc"
permute(list(msg), 0, len(msg))
print(out)

Function permute() takes Python list as input. So you have to convert the given string into list using list() function. Use the join() method to convert the list into the string.

Output:

['abc', 'acb', 'bac', 'bca', 'cba', 'cab']

This is the simple program you can write to get all the permutation in Python without itertools.