How to Get All the Combination of Upper and Lower of a String Python

In this post, we will see how to list out all permutations of a string in Python.

For example, the string ABC has 6 permutations, i.e., ABC, ACB, BAC, BCA, CBA, CAB.

Practice this problem

In Python, we can use the built-in module itertools to get permutations of elements in the list using the permutations() function.

import itertools if __name__ == '__main__' : s = 'ABC' nums = list ( s ) permutations = list ( itertools . permutations ( nums ) ) # Output: ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA'] print ( [ '' . join ( permutation ) for permutation in permutations ] )

However, we can also write your utility function to generate all permutations of a string. We can do this either recursively or iteratively.

1. Recursive Implementation

The idea is to convert the given string to a character array, and in-place generate all its permutations using backtracking.

We can do this by swapping each of the remaining characters in the string with its first character and generating all the permutations of the remaining characters using a recursive call. This is illustrated in the recursion tree shown below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

# Function to swap two characters in a character array def swap ( ch , i , j ) : temp = ch [ i ] ch [ i ] = ch [ j ] ch [ j ] = temp # Recursive function to generate all permutations of a string def permutations ( ch , curr_index = 0 ) : if curr_index == len ( ch ) - 1 : print ( '' . join ( ch ) ) for i in range ( curr_index , len ( ch ) ) : swap ( ch , curr_index , i ) permutations ( ch , curr_index + 1 ) swap ( ch , curr_index , i ) if __name__ == '__main__' : s = 'ABC' permutations ( list ( s ) )

Download  Run Code

Output:

ABC
ACB
BAC
BCA
CBA
CAB

Here's another implementation in Python which doesn't convert the string to a character array.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

# Recursive function to generate all permutations of a string def permutations ( remaining , candidate = '' ) : if len ( remaining ) == 0 : print ( candidate ) for i in range ( len ( remaining ) ) : newCandidate = candidate + remaining [ i ] newRemaining = remaining [ 0 : i ] + remaining [ i + 1 : ] permutations ( newRemaining , newCandidate ) if __name__ == '__main__' : s = 'ABC' permutations ( s )

Download  Run Code

Output:

ABC
ACB
BAC
BCA
CBA
CAB

2. Iterative Implementation

The idea is to store the partially generated permutations and then use those partial permutations to generate the final permutations in further iterations. Here's how the code would look like:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

# Iterative function to generate all permutations of a string in Python def permutations ( s ) : # base case if not s : return [ ] # create a list to store (partial) permutations partial = [ ] # initialize the list with the first character of the string partial . append ( s [ 0 ] ) # do for every character of the specified string for i in range ( 1 , len ( s ) ) : # consider previously constructed partial permutation one by one # iterate backward for j in reversed ( range ( len ( partial ) ) ) : # remove the current partial permutation from the list curr = partial . pop ( j ) # Insert the next character of the specified string into all # possible positions of current partial permutation. # Then insert each of these newly constructed strings into the list for k in range ( len ( curr ) + 1 ) : partial . append ( curr [ : k ] + s [ i ] + curr [ k : ] ) print ( partial , end = '' ) if __name__ == '__main__' : s = 'ABC' permutations ( s )

Download  Run Code

Output:

['CAB', 'ACB', 'ABC', 'CBA', 'BCA', 'BAC']

The time complexity of the above solutions is O(n.n!) since there are n! permutations for a string of length n, and each permutation takes O(n) time.

Thanks for reading.

Please use our online compiler to post code in comments using C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.

Like us? Refer us to your friends and help us grow. Happy coding 🙂

How to Get All the Combination of Upper and Lower of a String Python

Source: https://www.techiedelight.com/find-all-permutations-string-python/

Share this post