使用递归在 Scheme 中进行排列 [英] permutation in Scheme using recursion

问题描述

我发现了以下一段代码，它在 Scheme 中进行了排列.我的意思是，如果我输入类似参数 '(1 2 3) 它会给我:

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))

代码如下:

(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)))))

第一个函数remove，看起来很简单，通过将它与列表的开头进行比较并与它的其余部分递归调用，只删除由x表示的字符，即使它重复与否.

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.

我不太明白的部分是置换函数.据我所知，map 将函数应用于参数的每个元素(在本例中为列表)，而 apply 仅将一个函数完全应用于所有参数一次.那么这一行到底在做什么:

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)))))

对我来说，它似乎只是想创建一个包含两个元素的对:i 和 j，它们将成为一个元素排列的列表(如果我们假设列表只是一堆连接对).但是再次调用以 i 进行置换和删除的部分，那部分在做什么?它只是删除列表的头部以生成列表的子集，该子集的头部元素 i 是固定的，直到它用完元素?

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?

有什么帮助吗?

谢谢

推荐答案

让我们从内而外地拆解一下.修复 lst 并将内部表达式应用于其元素之一.

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))

看起来不错:内部表达式以递归方式删除和元素并生成列表剩余部分的排列.现在在这些排列上map lambda:

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))

所以内部 map 产生所有以一些 i 开头的排列，我们在这里设置为 1.

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

外部 map 确保所有排列都是通过将 lst 的所有元素视为第一个元素来生成的.

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)))

但这会生成嵌套过多的列表.应用 append 使列表列表变平，

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.

这篇关于使用递归在 Scheme 中进行排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！