<jupyter_start><jupyter_text>SICP 习题 (2.32)解题总结 : 产生列表子集的subsets过程 SICP  习题 2.32 理解起来有点麻烦，题目要求我们完成过程subsets，用于生产一个列表的子集。有关子集的概念应该比较简单，这里就不详细阐述了。题目给出了一个代码框架，要求我们完成map过程里的lambda定义，下面代码中部分是需要我们补充的。     (define (subsets s)      (if (null? s)          '(())          (let ((rest (subsets (cdr s))))        (append rest                  rest))))) 我们先从代码框架上理解一下出题者的思路，代码框架里关键的点是subsets的递归调用。当递归到列表末尾的时候返回一个只有空集一个元素的列表，这个要注意，不是空集，是只有空集一个元素的列表。接着我们来看倒数第一个元素，按题要求我们处理的样例(1 2 3)来看，这时rest应该是(())，而s应该是(3)，我们要构建出来的应该是包含3和()的子集，就是(() (3))。这时候还不是很明显可以理解这个代码框架，我们继续看倒数第二个元素，就是2，这个时候rest已经是(() (3))了，而s是（2 3），我们需要做的是将2和(() (3))里的每一个元素组合，然后再加上(() (3))中的两个元素，就是得出( () (3) (2) (2 3))这四个。我们知道2可以通过(car s)求得，而(cons (car s) i)可以将(car s)和列表i组合起来对应的，下面的代码就可以将(car s)和rest中的每一个元素组合起来，按上面的例子，下面的代码会生成((2) (2 3))    (map (lambda (i)                   (cons (car s) i))                 rest)接着，通过代码框架的append可以将原来的子集和新生成的子集合起来，按上面的例子就是将(() (3))   和  ((2) (2 3))组合成新的列表，就是结果(() (3) (2) (2 3))：    (append rest 		(map (lambda (i)		       (cons (car s) i))		     rest))所以最终的代码如下：<jupyter_code>(define (subsets s)
  (if (null? s)
      '(())
      (let ((rest (subsets (cdr s))))
	(append rest 
		(map (lambda (i)
		       (cons (car s) i))
		     rest)))))
(subsets '(a b c d e))<jupyter_output><empty_output><jupyter_text>另外，如果对以上说明理解不是很透彻，可以使用下面的debug版的subsets来试试。其实就是在处理过程中加入了很多display输出，让我们看明白每一步是如何处理的。print是一个非常有效的调试方法，不管你是在写java, 写c，还是写汇编。<jupyter_code>(define (subsets-debug s)
  (newline)
  (display "handling:")
  (display s)
  (if (null? s)
      '(())
      (let ((rest (subsets-debug (cdr s))))
	(let ((result (append rest (map (lambda (i)
					  (newline)
					  (display "trying to cons:")
					  (display (car s))
					  (display " ")
					  (display i)
					  (cons (car s) i))
					rest))))
	  (newline)(display "now rest is:") (display result) (newline)
	  result
	  ))))
(subsets-debug '(a b c d e))<jupyter_output>handling:(a b c d e)
handling:(b c d e)
handling:(c d e)
handling:(d e)
handling:(e)
handling:()
trying to cons:e ()
now rest is:(() (e))

trying to cons:d ()
trying to cons:d (e)
now rest is:(() (e) (d) (d e))

trying to cons:c ()
trying to cons:c (e)
trying to cons:c (d)
trying to cons:c (d e)
now rest is:(() (e) (d) (d e) (c) (c e) (c d) (c d e))

trying to cons:b ()
trying to cons:b (e)
trying to cons:b (d)
trying to cons:b (d e)
trying to cons:b (c)
trying to cons:b (c e)
trying to cons:b (c d)
trying to cons:b (c d e)
now rest is:(() (e) (d) (d e) (c) (c e) (c d) (c d e) (b) (b e) (b d) (b d e) (b c) (b c e) (b c d) (b c d e))

trying to cons:a ()
trying to cons:a (e)
trying to cons:a (d)
trying to cons:a (d e)
trying to cons:a (c)
trying to cons:a (c e)
trying to cons:a (c d)
trying to cons:a (c d e)
trying to cons:a (b)
trying to cons:a (b e)
trying to cons:a (b d)
trying to cons:a (b d e)
trying to cons:a (b c)
trying to cons:a (b c e)
trying to cons:a (b c d)
trying to cons:[...]
{'fraction_non_alphanumeric': 0.17687543014452856, 'fraction_numerical': 0.012044046799724708, 'mean_word_length': 3.773399014778325, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '282295', 'license': 'MIT', 'n_tokens_mistral': 1648, 'n_tokens_neox': 1637, 'n_words': 362, 'path': 'cn/.ipynb_checkpoints/sicp-2-32-checkpoint.ipynb', 'repo_name': 'DamonDeng/sicp_exercise', 'size': '2906'}