Assignment 4

Assignment 4

Dates

Assigned: November 13, 2019

Due: November 25, 2019

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:

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 you did in yesterday's lab. The main difference is this assignment deals with permuting a list of numbers, while the lab 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.

Note the 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.

Here's the extended version of that advice, with a head start and some hints:

• Head start: in Moodle you will find my complete lab code from yesterday.
• The permutations function will replace the alternative-words function from the lab, it will call 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.
• 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.

Submission and Grading

Submit your program with an .rkt extension via Moodle. The program will be graded using the usual programming rubric.