# 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 the`assign4.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.