permutation in Scheme using recursion

Question

I have found the following piece of code that it makes permutation in Scheme. I mean if I enter like arguments '(1 2 3) it will give me:

((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

The code is the following:

(define (remove x lst)
  (cond
    ((null? lst) '())
    ((= x (car lst))(remove x (cdr lst)))
    (else (cons (car lst) (remove x (cdr lst))))))

(define (permute lst)
  (cond
    ((= (length lst) 1)(list lst))
    (else (apply append(map(lambda (i) (map (lambda (j)(cons i j))
                                            (permute (remove i lst))))lst)))))

The first function remove, it seems straightforward that only gets rid of the caracter denoted by x, even if its repeated or not, by comparing it with the beginning of the list and calling recursively with the rest of it.

The part that I quite do not get it, is the permute function. For what I know map appies a function to every element of an argument (in this case a list), and apply just applies one function one time completely to all the arguments. So what is exactly doing this line:

(apply append(map(lambda (i) (map (lambda (j)(cons i j))
                                                (permute (remove i lst))))lst)))))

For me it seems that it just wants to create a pair with two elements: i and j, which they will become a list with the elements permuted (if we take the assumption that a list is just a bunch of concatenated pairs). But the part that calls again to permute and remove with i, what is that part doing? It is just removing the head of the list to generate subsets of the list having the head of the pair, element i, fixed until it runs out of elements?

Any help?

Thanks

Answer 1

Let's pick this apart, going from the inside out. Fix lst and apply the inner expression to one of its elements.

> (define lst '(1 2 3))
> (define i 1)
> (permute (remove i lst))
((2 3) (3 2))

Looks good: the inner expression removes an element and generates permutations of the remainder of the list, recursively. Now map the lambda over these permutations:

> (map (lambda (j) (cons i j)) (permute (remove i lst)))
((1 2 3) (1 3 2))

So the inner map produces all permutations that start with some i, which we've set to 1 here.

The outer map makes sure all permutations are generated by considering all elements of lst as the first element.

> (map (lambda (i) (map (lambda (j) (cons i j))
>                       (permute (remove i lst))))
>      lst)
(((1 2 3) (1 3 2)) ((2 1 3) (2 3 1)) ((3 1 2) (3 2 1)))

But this generates lists with too much nesting. Applying append flattens a list of lists,

> (append '(1 2) '(3 4) '(5 6))
(1 2 3 4 5 6)
> (apply append '((1 2) (3 4) (5 6)))
(1 2 3 4 5 6)

so we get a flat list of permutations out.