Assignment 4 - Spring 2019

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

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

  2. Open a browser and copy/paste this URL: https://classroom.github.com/a/uipczOKs

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

  4. Open a terminal window.

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


  6. 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!

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