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.
Source: Mathword()Below are the permutations of string ABC.
ABC, ACB, BAC, BCA, CAB, CBAHere is a solution using backtracking.
- C/C++
- Python
# Python program to print all permutations with# duplicates allowed# Function to swap valuesdef swap(a,l,r): t = a[l] a[l] = a[r] a[r] = t return adef toList(string): List = [] for x in string: List.append(x) return Listdef toString(List): return ''.join(List)# Function to print permutations of string# This function takes three parameters:# 1. String# 2. Starting index of the string# 3. Ending index of the string.def permute(a, l, r): if l==r: print toString(a) else: for i in xrange(l,r+1): a = swap(a,l,i) permute(a, l+1, r) a = swap(a,l,i) # backtrack# Driver program to test the above functionstring = "ABC"n = len(string)a = toList(string)permute(a, 0, n-1)# This code is contributed by Bhavya Jain
ABCACBBACBCACBACAB
Algorithm Paradigm: Backtracking
Time Complexity: O(n*n!)Please write comments if you find the above codes/algorithms incorrect, or find other ways to solve the same problem.