permutation in Scheme using recursion

问题:

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

回答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 and 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.

回答2:

I've always found it easier to understand the algorithm on a higher level before diving into an implementation and trying to understand what's happening there. So the question is: what are the permutations of a list, and how would you find them?

The permutations of a single element list are evidently just the list itself.

The permutations of (a b) are the set [(a b) (b a)].

The permutations of (a b c) are the set

[(a b c) (a c b) (b c a) (b a c) (c a b) (c b a)]

In general there are n! permutations of a list of length n - we have n choices for the first element, and once we've picked that, (n-1) choices for the second element, (n-2) for the third element, and so on. This decrease in the degrees of freedom as we fix more and more of the first elements of the list is very suggestive: maybe we can represent the finding the permutations of a list of length n in terms of the permutations of a list of length (n - 1), and so on until we reach the permutations of a single-element list.

It turns out that the permutations of a list a precisely the set [element prepended to the permutations of list \ element, for every element in list].

Looking at the (a b c) case confirms that this is true - we have a preceding (b c) and (c b), which are the permutations of (b c), b preceding (a c) and (c a) and so on. This operation of prepending the element to the sublist could be defined as

(define (prepend j)
  (cons element j))

and the operation of doing it for all the permutations of the sublist would then be (map prepend (permute sublist)). Now, defining a new prepend function for each element is maybe overkill - especially since they all have the same form. So a better approach is just to use a lambda, which captures the value of the element under consideration. The desired operation is then (map (lambda (j) (cons element j)) (permute sublist)). Now, we want to apply this operation to each element of the list, and the way to do that is using another map, giving:

(map (lambda (element)
       (lambda (j) (cons element j) (permute sublist)))
     list)

Now, this looks good, but there is a problem: each stage of the recursion takes single elements and turns them into a list. That's fine for lists of length 1, but for longer lists it repeats for every recursive call, and we get very deeply nested lists. What we really want to do is to put all these lists on the same footing, which is exactly what the (apply append ...) takes care of. And that's almost all of that line. The only thing missing is how the sublist is generated in the first place. But that's easy as well - we'll just use remove, so that sublist = (remove element list). Putting everything together, and we have

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

The base case takes care of the length = 1 case, and all of the others can be found from there