creating permutation of a list in scheme
list, permutation, recursion, scheme
Solution
The permutation algorithm isn't as simple as you imagine, it'll be really, really tricky to write just in terms of the basic list operations you mention, unless you write your own helpers that mirror built-in functions such as `map`, `append` (but why not use the built-ins in the first place?).
To get an idea of what needs to be done, take a look at the Rosetta Code page describing several possible solutions, look under the Scheme or Racket links. Here's an adaptation of one of the implementations from scratch shown in the linked page - and besides the basic list operations mentioned in the question, it uses `append` and `map`:
(define (permutations s)
(cond [(empty? s) empty]
[(empty? (rest s)) (list s)]
[else
(let splice [(l '()) (m (first s)) (r (rest s))]
(append
(map (lambda (x) (cons m x))
(permutations (append l r)))
(if (empty? r)
empty
(splice (cons m l) (car r) (cdr r)))))]))
See how it works:
(permutations '(1 2 3))
=> '((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 2 1) (3 1 2))
Problem
I'm trying to write a function that creates the permutation of a list using just the basic list constructs (cons, empty, first, rest). I'm thinking of inserting the first value of the list everywhere in the recursive call of the rest of the list, but I'm having some trouble with my base case. My code: ``` (define (permutation lst) (cond [(empty? lst) (cons empty empty)] [else (insert_everywhere (first lst) (permutation (rest lst)))])) ``` (permutation (list 1 2)) gives me (list 1 2 empty 2 1 empty). Is there anything I can do to create a placeholder (such as empty) between the different combinations but not have the program interpret the placeholder as an element in the list? Is my base case right? Thanks!