Lab 10: Recursion 🔐
Due Date and Submission Requirements
- Due Date: Thursday, November 7th at 11:59 p.m.
- Partner Information: This is an individual assignment. You are allowed to collaborate with other students, but each student must submit their individual, independent solution.
- Submission Instructions: Submit your Lab10Demo.java file to the appropriate D2L dropbox.
The goal of this lab is:
- Write basic recursive methods
Background Information
In computer science, generating permutations is a common task that involves arranging a set of items in every possible order.
This technique can be especially relevant in password cracking, where the goal is to try every possible combination of characters until the correct password is found.
This lab will focus on using recursion to generate all permutations of a given set of characters (like those in a password) to simulate this process.
For example, for the characters "abc", the permutations include:
In this lab, we will be attempting to crack the password of an individual who adores his two dogs, Max and Andy.
We are pretty sure that his password is some permutation of one of the two names, so we must generate all possible permutations of their names in order to gain access to his computer.
Directions
Using Lab10Demo.java as a starting point, you will fill in the body of the generate_permutations and the print_permutations_recursive method. You cannot modify anything in the main() method.
The generate_permutations method recursively generates all permutations. This method MUST use recursion.
generate_permutations takes the following parameters:
- String[] characters: An array of characters from which to generate permutations
- String perm: A string that accumulates the current permutation being constructed
- List<String> list: A list that stores all generated permutations
The print_permutations_recursive prints each permutation in the order it was generated. This method MUST use recursion.
print_permutations_recursive takes the following parameters:
- List<String> list: A list of permutations to be printed
Starting Code
Output
When you run your program, your output should look exactly like this: sample output.
Hints
- In the generate_permutations method, you can use perm.contains(characters[i]) to check if the character has already been included in the current permutation
- In the print_permutations_recursive method, use list.remove(0) to get the first permutation and ensure it is printed in the correct order
Grading (10 points)
- 5 points - the generate_permutations method correctly generates all permutations of the input array and uses recursion
- 5 points - The print_permutations_recursive method correctly prints the permutations in the order they are generated and uses recursion