Authors:
Y Daniel Lang
Chapter:
5.recursion
Exercise:
Programming Excercises
Question:23 | ISBN:978013274719 | Edition: 6
Question
(String permutation) Write a recursive function to print all the permutations of a string. For example, for the string abc, the printout is:
abc
acb
bac
bca
cab
cba
(Hint: Define the following two functions. The second function is a helper function.
def displayPermuation(s):
def displayPermuationHelper(s1, s2):
The first function simply invokes displayPermuation(" ", s). The second function uses a loop to move a character from s2 to s1 and recursively invokes it with a new s1 and s2. The base case is that s2 is empty and prints s1 to the console.)
Write a test program that prompts the user to enter a string and displays all its permutations.
Answer
String Permutation Program Code:
# Recursive function to display all permutations of a string.
def displayPermutation(s):
displayPermutationHelper("", s)
#Recursive helper function to display all permutations of a string.
def displayPermutationHelper(s1, s2):
if s2 == "":
# Base case: If s2 is empty,
#have generated a complete permutation
print(s1)
else:
# Recursive case: Iterate through each character in s2
for i in range(len(s2)):
# Move the current character from s2 to s1
new_s1 = s1 + s2[i]
new_s2 = s2[:i] + s2[i+1:]
# Recursively generate permutations with the updated s1 and s2
displayPermutationHelper(new_s1, new_s2)
# Prompt the user for input
string = input("Enter a string: ")
# Display all permutations of the input string
print("All permutations of the string:")
displayPermutation(string)
Executed Output:
Enter a string: abc
All permutations of the string:
abc
acb
bac
bca
cab
cba