# Assignment 4 - Spring 2019

## Permutations

**Assigned:** Wed, Apr 3

**Due:** Wed, Apr 17

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

- Use your CS account to login to one of the Linux workstations in the classroom or Asprey Lab.

- Login to Github and you will be prompted to accept this assignment
- Note: this will create your own copy of Assignment 4 for you to work on, but it's not on your Linux account yet

- Open a terminal window.

- Create a new directory for this assignment in your cs101 directory by entering the following at the Linux prompt:
$ cd cs101 $ mkdir assign4 $ cd assign4

- Type the following commands to pull down a copy of this lab from GitHub:
$ git init $ git remote add origin https://github.com/Vassar-cs101-mlsmith-spr2019/assignment-4-yourGitHubID $ git pull origin master

### 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 6.10 [3m]. 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`assign3.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 a terminal window, type the following commands at the Linux prompt:

$ git commit -m "finished assign4.rkt" assign4.rkt $ git push -u origin master