Code: Select all
;; insert: num (listof num) -> (listof (listof num))
;; inserts a number before, after and between every number in a list
(check-expect (insert 2 '(3)) '((2 3) (3 2)))
(check-expect (insert 1 '(2 3)) '((1 2 3) (2 1 3) (2 3 1)))
(define (insert n lst)
[(empty? lst) (cons n empty)]
(cons (cons n lst)
(list (cons (first lst) (insert n (rest lst)))))]))
This holds for 2 numbers, but breaks for anything higher. The second example actually gives:
'((1 2 3) (2 (3 1) (1 3)))
So the problem is where I call insert again recursively: It does indeed find every combination of 1 and 3, but it appends both one after the other after 2, instead of putting a 2 in front of each one.
I can't figure out how to get this to work, and it is frustrating as hell. Can anyone give me some tips for getting it to work? I thought I knew recursion just fine, but having to do this with these strange lists is throwing me off.