1. (String permutation) Write a recursive method to print all the permutations o
ID: 3763845 • Letter: 1
Question
1. (String permutation) Write a recursive method to print all the permutations of a string. For example, for a string abc, the printout is:
abc
acb
bac
bca
cab
cba
Hint:
Declare the following two methods. The second is a helper method.
public static void displayPermutation(String s)
public static void displayPermutation(String s1, String s2)
The first method simply invokes displayPermutation("", s). The second method uses a loop to move a character from s2 to s1 and recursively invoke it with a new s1 and s2. The base case is that s2 is empty and prints s1 to the console.
2. (Printing problem) A Scottish tartan is a pattern consisting of cross-crossed horizontal and vertical colors. See sample final exam for solution.
a. You have to implement a program that prints the tartan of the Young McJava clan that takes a number n as input and prints a matrix of n rows and n columns of interleaved vertical and horizontal n and n-1 separated with spaces, starting with n, without using loops. You are allowed to use only recursion.
Examples:
tartan(4) prints:
4 3 4 3
3 4 3 4
4 3 4 3
3 4 3 4
tartan(5) prints:
5 4 5 4 5
4 5 4 5 4
5 4 5 4 5
4 5 4 5 4
5 4 5 4 5
b. Implement the YoungMcJava program using for loops.
Note: the last lab of the semester (Lab 26) will be used for project submission.
Explanation / Answer
permutations of a string:
public class MainClass
{
public static void main(String args[])
{
permuteString("", "ABCD");
}
public static void permuteString(String beginningString, String endingString)
{
if (endingString.length() <= 1)
System.out.println(beginningString + endingString);
else
for (int k = 0; k < endingString.length(); k++)
{
try
{
String newString = endingString.substring(0, i) + endingString.substring(i + 1);
permuteString(beginningString + endingString.charAt(i), newString);
}
catch (StringIndexOutOfBoundsException exception)
{
exception.printStackTrace();
}
}
}
}
public class YoungMcJava
{
public static void main(String[] args)
{
tartan(3);
tartan(4);
}
public static void tartan(int n)
{
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<=n; j++)
{
System.out.print(((i+j)%2==0?n:n-1)+" ");
}
System.out.println();
}
}
}
"recursion".
public class YoungMcJava
{
public static void tartan(int n)
{
tartan2(1,n);
}
public static void tartan2(int i, int n)
{
if(i==n+1)
{
return;
}
else
{
tartan_row(i,1,n);
tartan2(i+1,n);
}
}
public static void tartan_row(int i, int j, int n)
{
if(j==n+1)
{
System.out.println();
return;
}
else
{
System.out.print(((i+j)%2==0?n:n-1)+" ");
tartan_row(i,j+1,n);
}
}
public static void main(String[] args)
{
tartan(4);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.