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
# Function to find permutations of a given stringfrom itertools import permutationsdef allPermutations(str): # Get all permutations of string 'ABC' permList = permutations(str) # print all permutations for perm in list(permList): print (''.join(perm)) # Driver programif __name__ == "__main__": str = 'ABC' allPermutations(str) |
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 permutationsimport strings = "GEEK"a = string.ascii_lettersp = permutations(s)# Create a dictionaryd = []for i in list(p): # Print only if not in dictionary if (i not in d): d.append(i) print(''.join(i)) |
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!)
Approach: Using Recursion
This code generates all possible permutations of a given string using recursion.
Algorithm
1. Take input string from the user
2. Define a recursive function to generate all possible permutations of the given string
3. Base case: If the length of the input string is 1, return the string
4. Recursive case: For each character in the string, fix it and recursively find all the permutations of the remaining characters
5. Combine the fixed character with each of the permutations obtained from the recursive call and append it to the list of permutations
6. Return the list of permutations
Python3
def generate_permutations(string): if len(string) == 1: return [string] permutations = [] for i in range(len(string)): fixed_char = string[i] remaining_chars = string[:i] + string[i+1:] for perm in generate_permutations(remaining_chars): permutations.append(fixed_char + perm) return permutationsstring ='GEEK'permutations_list = generate_permutations(string)z=set(permutations_list)for perm in z: print(perm) |
GKEE KEEG KEGE KGEE EKGE EGEK EEGK GEKE EGKE EKEG GEEK EEKG
Time complexity: O(n*n!), where n is the length of the input string.
Auxiliary Space: O(n*n!).
