1 12687dd9 2023-08-04 jrmu ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 12687dd9 2023-08-04 jrmu ;; about the language level of this file in a form that our tools can easily process.
3 12687dd9 2023-08-04 jrmu #reader(lib "htdp-intermediate-reader.ss" "lang")((modname 17.6.5) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "dir.ss" "teachpack" "htdp") (lib "hangman.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "dir.ss" "teachpack" "htdp") (lib "hangman.ss" "teachpack" "htdp")))))
4 12687dd9 2023-08-04 jrmu ;A list-of-names is either
6 12687dd9 2023-08-04 jrmu ;2. (cons s lon)
7 12687dd9 2023-08-04 jrmu ;where s is a symbol and lon is a list-of-names.
9 12687dd9 2023-08-04 jrmu ;A list-of-list-of-names is either
10 12687dd9 2023-08-04 jrmu ;1. empty, or
11 12687dd9 2023-08-04 jrmu ;2. (cons lon lolon)
12 12687dd9 2023-08-04 jrmu ;where lon is a list-of-names and lolon is a list-of-list-of-names.
14 12687dd9 2023-08-04 jrmu ;gift-pick : list-of-names -> list-of-names
15 12687dd9 2023-08-04 jrmu ;Given names, return a randomly picked re-arrangement of list-of-names where not a single name is found in an identical position in the new list as in alon.
17 12687dd9 2023-08-04 jrmu (define (gift-pick names)
18 12687dd9 2023-08-04 jrmu (random-pick
19 12687dd9 2023-08-04 jrmu (non-same names (arrangements names))))
21 12687dd9 2023-08-04 jrmu ;random-pick : list-of-list-of-names -> list-of-names
22 12687dd9 2023-08-04 jrmu ;Given a-lolon, pick one list-of-names randomly.
24 12687dd9 2023-08-04 jrmu (define (random-pick a-lolon)
25 12687dd9 2023-08-04 jrmu (pick-nth a-lolon (+ 1 (random (length a-lolon)))))
27 12687dd9 2023-08-04 jrmu ;pick-nth : list-of-list-of-names N[>=1] -> list-of-names
28 12687dd9 2023-08-04 jrmu ;Given a-lolon, pick the n-th list-of-names. The first list-of-names has an index of 1.
30 12687dd9 2023-08-04 jrmu (define (pick-nth a-lolon n)
32 12687dd9 2023-08-04 jrmu [(empty? a-lolon) (error 'pick-nth "Unexpected error")]
33 12687dd9 2023-08-04 jrmu [(= n 1) (first a-lolon)]
34 12687dd9 2023-08-04 jrmu [(> n 1) (pick-nth (rest a-lolon) (sub1 n))]))
36 12687dd9 2023-08-04 jrmu ;non-same : list-of-names list-of-list-of-names -> list-of-list-of-names
37 12687dd9 2023-08-04 jrmu ;Given a-lon and a-lolon, return all list-of-names within a-lolon for those list-of-names where not a single name occupies the same position in the index as in a-lon.
39 12687dd9 2023-08-04 jrmu (define (non-same a-lon a-lolon)
41 12687dd9 2023-08-04 jrmu [(empty? a-lolon) empty]
42 12687dd9 2023-08-04 jrmu [(no-common-index? (first a-lolon) a-lon) (append (list (first a-lolon))
43 12687dd9 2023-08-04 jrmu (non-same a-lon (rest a-lolon)))]
44 12687dd9 2023-08-04 jrmu [else (non-same a-lon (rest a-lolon))]))
46 12687dd9 2023-08-04 jrmu ;no-common-index? : list-of-names list-of-names -> boolean
47 12687dd9 2023-08-04 jrmu ;Given lon1 and lon2, return true if not a single name occupies the same index in lon1 and lon2. False otherwise.
48 12687dd9 2023-08-04 jrmu ;ASSUMPTION: Both lists are of the same length.
50 12687dd9 2023-08-04 jrmu (define (no-common-index? lon1 lon2)
52 12687dd9 2023-08-04 jrmu [(empty? lon1) true]
53 12687dd9 2023-08-04 jrmu [(symbol=? (first lon1) (first lon2)) false]
54 12687dd9 2023-08-04 jrmu [else (no-common-index? (rest lon1) (rest lon2))]))
56 12687dd9 2023-08-04 jrmu ;arrangements : list-of-names -> list-of-list-of-names
57 12687dd9 2023-08-04 jrmu ;Given names (a list-of-names), return all permutations of the names.
59 12687dd9 2023-08-04 jrmu (define (arrangements names)
61 12687dd9 2023-08-04 jrmu [(empty? names) (list empty)]
62 12687dd9 2023-08-04 jrmu [else (insert-in-lolon (first names) (arrangements (rest names)))]))
64 12687dd9 2023-08-04 jrmu ;insert-in-lolon : symbol list-of-list-of-names -> list-of-list-of-names
65 12687dd9 2023-08-04 jrmu ;Given a-symbol and a-lolon, insert a-symbol into every position in each list-of-names element within a-lolon to return a new list-of-list-of-names.
67 12687dd9 2023-08-04 jrmu (define (insert-in-lolon a-symbol a-lolon)
69 12687dd9 2023-08-04 jrmu [(empty? a-lolon) empty]
70 12687dd9 2023-08-04 jrmu [(cons? a-lolon)
71 12687dd9 2023-08-04 jrmu (append (insert-name a-symbol (first a-lolon) (length (first a-lolon)))
72 12687dd9 2023-08-04 jrmu (insert-in-lolon a-symbol (rest a-lolon)))]))
74 12687dd9 2023-08-04 jrmu ;insert-name : symbol list-of-names N[>=0] -> list-of-list-of-names
75 12687dd9 2023-08-04 jrmu ;Given a-symbol, insert it into every position in names starting at the n-th position, continuing to the very beginning of the list-of-names (n=0), to return a list-of-list-of-names.
77 12687dd9 2023-08-04 jrmu (define (insert-name a-symbol names n)
79 12687dd9 2023-08-04 jrmu [(= n 0) (list (insert-name-at-posn a-symbol names n))]
80 12687dd9 2023-08-04 jrmu [(cons? names) (append (list (insert-name-at-posn a-symbol names n))
81 12687dd9 2023-08-04 jrmu (insert-name a-symbol names (sub1 n)))]
82 12687dd9 2023-08-04 jrmu [(empty? names) (error 'insert-name "unexpected error")]))
84 12687dd9 2023-08-04 jrmu ;insert-name-at-posn : symbol list-of-names N[>=0] -> list-of-names
85 12687dd9 2023-08-04 jrmu ;Given a-symbol (symbol), names (list-of-names), and n (N[>=0]), insert a-symbol into names at the n-th position and return the list-of-names.
87 12687dd9 2023-08-04 jrmu (define (insert-name-at-posn a-symbol names n)
89 12687dd9 2023-08-04 jrmu [(= n 0) (append (list a-symbol) names)]
90 12687dd9 2023-08-04 jrmu [(cons? names) (append (list (first names))
91 12687dd9 2023-08-04 jrmu (insert-name-at-posn a-symbol (rest names) (sub1 n)))]
92 12687dd9 2023-08-04 jrmu [(empty? names) (error 'insert-name-at-posn "list too short")]))
