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;
}