Решение упражнения 2.32 из SICP

29 January, 2008 (23:20) | Решения упражнений

Иногда возникает ощущение, что авторы СИКП (Структуры и интерпретации компьютерных программ) специально упрощают нам жизнь, делая большую часть упражнения за нас. В данном случае структура процедуры, строящей множество всех подмножеств уже задана. Нам нужно лишь вписать маленькую часть.

Логика процедуры следующая. Чтобы получить все подмножества множества из N элементов, выделим первый элемент, получим все подмножества исходного множества без этого элемента, а теперь запишем их в ответ дважды: сначала просто как есть, а затем с добавлением выделенного первого элемента к каждому из подмножеств.

Например для множества {1, 2, 3} выделяем элемент 1 и для множества {2, 3} получаем такие подмножества: {}, {3}, {2}, {2, 3}. Значит все подмножества исходного множества {1, 2, 3} – это, во-первых, полученные 4 множества {}, {3}, {2}, {2, 3}, а также они же с добавленной (напимер, в начало) единицей: {1}, {1, 3}, {1, 2}, {1, 2, 3}. То есть полный ответ: {}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}.

Именно этот подход реализует такая процедура:

(define (subsets s) 
  (if (null? s) 
      (list nil) 
      (let ((rest (subsets (cdr s)))) 
        (append rest (map (lambda (ss) (cons (car s) ss)) rest)))))

Как видим, вместо <??> вписана процедура

(lambda (ss) (cons (car s) ss)),

где ss – это очередное подмножество, полученное из списка (subsets (cdr s)), а (car s) – это тот самый выделенный первый элемент исходного множества.

Write a comment