Objectives
_ Creating and compiling a simple program
_ Designing classes
_ Use of recursive algorithms
_ Learn basic combinatorics
Task: string permutation
Write a recursive method to print all permutations of a string. For example, for a string "abc", the output would be:
abc
acb
bac
bca
cab
cba
Write a program to test your method.
The program should prompt the user to enter a string. Then the program should display all the possible permutations. You can assume that all characters in the input string are different.
Hint:
Declare the following two helping methods:
void displayPermutations(String text)
and
void displayPermutations(String done, String todo)
The first method invokes displayPermutations( "", text ). The second method uses a loop to move a character from todo to done and recursively invokes it with a new todo and done. The base case is when todo string is empty. In this case the method prints done
Example
Note:
user entered values are shown in bold.
Example 1
This program prints out all permutations of a string.
Enter a string? dome
There are the following permutations:
dome
doem
dmoe
dmeo
deom
demo
odme
odem
omde
omed
oedm
oemd
mdoe
mdeo
mode
moed
medo
meod
edom
edmo
eodm
eomd
emdo
emod
Example 2
This program prints out all permutations of a string.
Enter a string? one
There are the following permutations:
one
oen
noe
neo
eon
eno
Important Notes
1. For the purposes of this assignment, you can assume that the user will only enter valid values.
2. In your program you must define and make use of at least the two methods:
a. displayPermutations(String text) and
b. displayPermutations(String done, String todo) as described above.
3. Test your program. In particular, be sure to test it on turing before you submit it.