Assignment 4 - Spring 2021
Permutations
Assigned: Wed, Apr 21
Due: Wed, May 5
For this assignment you will:
- Follow the Design Recipe to design a series of functions that computes all the permutations of a list of numbers
- Be sure to write tests for each function as you go, before you move on to the function of your wish list
- Have a total of four functions by the time you finish, at which point you can run you program for the first time
- Test your faith in the Design Recipe
Assignment Setup
- Login to Github and you will be prompted to accept this assignment
- After you click on the [Accept this assignment] button, you will see a new page display in your browser with the message:
- You accepted the assignment, Assignment 4. We're configuring your repository now. This may take a few minutes to complete. Refresh this page to see updates.
- After you refresh the page you should see a page with the message: “You're ready to go!”
- Note: this will create your own copy of Assignment 4 for you to work on, but it's not on your computer yet.
- Click on the URL where your assignment repository has been created: https://github.com/Vassar-cs101-mlsmith/assignment-4-yourGitHubID
- you are now on the GitHub page for your Assignment 4 repository
- Click on the green button to download your [Code]
- a “Clone” dialog box will appear, with the HTTPS tab underlined in red (if not, click on the HTTPS tab to select it)
- select the last option labeled “Download ZIP” and save it on your computer
- move the Assignment 4 zip file from its download location to your
cs101
course folder. - extract the contents of the zip file either by double-clicking on it or control-clicking on it and selecting the appropriate option to extract its contents
- navigate into your
assign4
folder and confirm you see theassign4.rkt
file there.
Background
The permutations of a list of numbers is the list of all possible sequences of those numbers. We will represent the permutations of a list of numbers as a list of lists of numbers. When your program is completed and correct, it will demonstrate the following behavior in the Interactions Pane of DrRacket:
Welcome to DrRacket, version 8.0 [cs]. Language: Intermediate Student; memory limit: 512 MB. All 12 tests passed! > (permutations '()) (list '()) > (permutations '(1)) (list (list 1)) > (permutations '(1 2)) (list (list 1 2) (list 2 1)) > (permutations '(1 2 3)) (list (list 1 2 3) (list 2 1 3) (list 2 3 1) (list 1 3 2) (list 3 1 2) (list 3 2 1)) >
Let's take a moment to describe the above sample behavior:
- The permutations of the empty list of numbers is a list containing the empty list of numbers.
- The permutations of a list containing one number is a list containing that list of one number.
Things get more interesting for larger lists:
- The permutations of a list containing two numbers is a list containing two lists:
- The first list is the original list of two numbers
- The second list is the original list of two numbers with their sequence reversed
- The permutations of a list containing three numbers is easier to describe using the above example as follows:
- first, find the permutations of the rest of the list, which is a list of lists of two numbers: (list '(2 3) '(3 2))
- next, insert the first number, 1, in front of, in between, and following the numbers in each list:
- (list '(1 2 3) '(2 1 3) '(2 3 1)) ⇐== 1 appears in front of, in between, and following the numbers in (list 2 3)
- (list '(1 3 2) '(3 1 2) '(3 2 1)) ⇐== 1 appears in front of, in between, and following the numbers in (list 3 2)
- finally,
append
the above two lists together into one list
Write the program
Note: this assignment is similar to the exercises described in HtDP/2e Section 12.4 of HtDP/2e. The main difference is this assignment deals with permuting a list of numbers, while the HtDP/2e version involves permuting a word (a list of one-character strings). It may help to reread this section of the text, with these differences in mind.
Here's some advice given in HtDP/2e for this assignment: The solution of this exercise is a series of functions. Patiently stick to the design recipe and systematically work through your wish list.
And here's my extended version of that advice, with a head start and some hints to help guide you:
- Head start: I've provided you with starter code in
assign4.rkt
, in which I've given you the first function,permutations
, fully implemented and complete in terms of the Design Recipe. - Hint #1: The
permutations
function calls a helper function,insert-everywhere/in-all-lons
, which you must design and implement using the Design Recipe. This helper function is on your wish list, and it is your starting point for working on this assignment. - Hint #2: The
insert-everywhere/in-all-lons
function will require a helper function:insert-everywhere/in-one-lon
. Put this function on your wish list to design next. - Hint #3: The
insert-everywhere/in-one-lon
function will require one final helper function, which I called:insert-beginning/of-all-lons
. Put this function on your wish list to design next. - Hint #4: You should be able to design and implement
insert-beginning/of-all-lons
without any further need for helper functions. Once you finish this function, your wish list will be empty!
Submitting your work
- From your browser on the GitHub page for your Assignment 4 repository, click on the [Add file] drop-down button and select “Upload files”
- From your assign4 folder on your desktop, click and drag the
assign4.rkt
file onto your browser where it says, “Drag files here to add them to your repository”- just below the region of the webpage you should see both files appear; they'll be just above the Commit Changes section of the page.
- You are now ready to commit changes! Click on the green [Commit changes] button.
- Your updated
assign4.rkt
file file should now be in your Assignment 4 GitHub repository.