====== Assignment 4 - Spring 2021 ======

~~NOTOC~~

===== 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 ====

  - Open a browser and copy/paste this URL: https://classroom.github.com/a/MOTfacIb \\ \\ 
  - 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:

<code scheme>
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))
> 
</code>

\\ 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 [[https://htdp.org/2018-01-06/Book/part_two.html#%28part._sec~3apermute%29|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.