Assignment 4 - Spring 2021

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

1. Open a browser and copy/paste this URL: https://classroom.github.com/a/MOTfacIb
   
   
2. Login to Github and you will be prompted to accept this assignment
   1. After you click on the [Accept this assignment] button, you will see a new page display in your browser with the message:
      1. 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.
   2. After you refresh the page you should see a page with the message: “You're ready to go!”
   3. Note: this will create your own copy of Assignment 4 for you to work on, but it's not on your computer yet.
      
      
3. Click on the URL where your assignment repository has been created: https://github.com/Vassar-cs101-mlsmith/assignment-4-yourGitHubID
   1. you are now on the GitHub page for your Assignment 4 repository
      
      
4. Click on the green button to download your [Code]
   1. a “Clone” dialog box will appear, with the HTTPS tab underlined in red (if not, click on the HTTPS tab to select it)
   2. select the last option labeled “Download ZIP” and save it on your computer
   3. move the Assignment 4 zip file from its download location to your cs101 course folder.
   4. 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
   5. navigate into your assign4 folder and confirm you see the assign4.rkt file there.
      

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

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!

• 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.