;; Solution to Scheme-Permutations exercise.

(define (list-one-to-n  n)
  (cond ((< n 1) '( ))
    ((= n 1) '(1) )
    (#t  (append (list-one-to-n (- n 1)) (list n))) ) )

(define (flatten lsts)
  (apply append lsts) )

(define (insert-at-k k elt lst)
  (cond 
     ((= k 0) (cons elt lst))
     ((pair? lst) 
      (cons (car lst) 
            (insert-at-k (- k 1) elt (cdr lst)) ) )
     (#t lst) ) )

(define (perms-one-to-n  n)
  (if (= n 1) '((1))
   (let ((indices (cons 0 (list-one-to-n (- n 1)))))
    (flatten 
     (map (lambda (old)
            (map (lambda (k) 
                   (insert-at-k k n old)) 
                 indices))
            (perms-one-to-n (- n 1)) ) ) ) ) )