SICP——嵌套映射

范围

程序: 嵌套映射结构 ;permutation

嵌套映射

主要介绍一种方法,将高级语言中多重循环的语句用嵌套映射的计算方式表达。

问题:给定自然数 n ,找出不同的序对 (i, j), 满足:$ 1 ≤ j ≤ i ≤ n $, 且 $ i + j $ 是素数。假定 n 为 6,则结果应该如下:

i j i+j
2 1 3
3 2 5
4 1 5
4 3 7
5 2 7
6 1 7
6 5 11

最自然的解法是;生成所有小于等于 n 的自然数的全序对,进行过滤,选出和为素数的序对。对通过过滤的序对,产生一个三元组(i, j, i + j)

在高级语言中会这样子产生序对:对于 $ i ≤ n $,枚举 $ j ≤ i $。

1
2
for(i = 1; i<= n; i++)
for(j = 1; j < i; j++)

用序列操作、以及映射的方式来讲这两个 for 语句所表达的东西,是如下一段有可能看起来觉得很绕的话:

对序列 (1 ~ n) 做一次映射:对这个序列里的每个 i,对序列(1 ~ i-1) 再做一次做映射,生成序对(list i j)。将所有序对用 append 积累起来,得到一个序对序列。

1
2
3
4
5
6
(accumulate append ;用 append 积累所有序对列表
nil
(map (lambda(i) ;外层映射是:for(i=1;i<=n;i++) 对 i 做映射
(map (lambda(j) (list i j)) ;内层映射是:for(j=1;j<i;j++) 生成list(i, j)
(enumerate-interval 1 (- i 1)))) ;外层映射看3、6行,内层映射看4、5行
(enumerate-interval 1 n))) ;这里 n 还未定义

accumulate append map 这一个程序(映射并用append做序列的表积累)定义为一个过程:

1
2
(define (flatmap proc seq)
(accumulate append nil (map proc seq)))

过滤找出和为素数的序对:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
;判断素数
(define (square x)
(* x x))
(define (smallest-divisor n)
(find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
(= (remainder b a) 0))
(define (prime? n)
(= n (smallest-divisor n)))
;判断一个序对的和是不是素数
;由于“序对”是使用 list 形成的表,所以要用 cadr 而不是 cdr
(define (prime-sum? pair)
(prime? (+ (car pair) (cadr pair))))

生成一个三元组:(i, j, i + j),代表 i 和 j 是一个和为素数的序对。

1
2
(define (make-pair-sum pair)
(list (car pair)(cdr pair)(+ (car pair)(cadr pair))))

整合起来的过程是:

1
2
3
4
5
6
7
8
9
10
(define (prime-sum-pairs n) ;
(map make-pair-sum ;对序列(1~n)做映射:生成和为素数的序对的三元组
(filter prime-sum? ;从序对的表中过滤,只挑和为素数的序对
(flatmap ;faltmap: 映射,并用把结果用 append 积累
(lambda(i) ;这一行的结果会是一个表,交给filter过滤
(map (lambda(j) (list i j)) ;嵌套映射的注释见上方
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))))
(prime-sum-pairs 6)

这个例子讲完了。是不是很神奇呢

下一个例子:全排列:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define (permutations s)
(if (null? s)
(list nil) ;如果 s 为空,s的全排列就为空。这也是递归的最终情况。
(flatmap
(lambda (x) ;外层映射是 for x in s,对 x 做一个映射
(map (lambda (p) (cons x p)) ;内层映射是对 p 生成 cons(x, p),p 是 s 中除外 x 的全排列
(permutations (remove x s))))
s)))
(define (remove item sequence) ; 返回除了指定 item 之外的所有项
(filter (lambda(x) (not (= x item)))
sequence))
(permutations (list 1 2 3))

对比一下C语言的全排列:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<stdio.h>
int a[10], book[10], n;//a数组代表盒子,book数组代表手中的卡的情况
void dfs(int posi)
{
int i;
if (posi == n + 1)//如果走到了第n+1个盒子(实际上没有n+1个盒子)说明前n个盒子已经都放好扑克牌
{
//输出一种全排列
for (i = 1; i <= n; i++)
printf("%d", a[i]);
printf("\n");
return;//一定要返回,回到最近一次调用dfs的地方
}
for (i = 1; i <= n; i++)//每个小盒子都可能放1、2、3、、、n的牌,用for循环
{
//判断编号为i的扑克牌是否还在手上
if (book[i] == 0)//book[i]==0说明i号扑克牌在手上
{
a[posi] = i;//丢到这个盒子里
book[i] = 1;//book[i]置为1,表示i号扑克牌不在手上
dfs(posi + 1);//走到下一个盒子前进行dfs
book[i] = 0;//非常重要的一步,完成了一次dfs一定要收回这张牌才可以进行下一次尝试
}
}
return;
}
int main()
{
printf("输入n,输出123……n的全排列:");
scanf_s("%d", &n);
dfs(1);//从第一个盒子开始dfs
getchar();
return 0;
}