Статьи / Задачи с решениями - часть вторая (Задача №2: Множество всех подмножеств)
В статье рассматривается 7 задач и предлагаются детали реализации.
Автор: Потапенко В.А.
Написал: artish   Дата: 2008-09-09 20:10
Комментарии: (0)   Рейтинг:
Задача: Множество всех подмножеств

Реализовать функцию, возвращающую множество всех подмножеств множества, поступившего в качестве аргумента.

Останемся в рамках оговоренного представления множеств. Проанализируем задачу:

Множество всех подмножеств пустого множества совпадает с ним самим. В любом другом случае можно получить множество всех подмножеств множества X путем присоединения элемента (car X) к
каждому элементу множества всех подмножеств множества (cdr X) + сами эти подмножества.

Для написания решения нам необходимо формализовать концепцию регулярной обработки данных, а именно: “применение некоторой функции к элементам некоторого списка”. Назовем реализацию функции mapcar~

Формализация может быть следующей:
 
(defun mapcar~ (function list)
(cond
((null list) nil)
(t (cons (funcall function (car list)) (mapcar~ function (cdr list)) ))
)
)
 

Тестирование:
 
> (mapcar~ #'(lambda (x) (+ x 5)) '(1 2 3 4 5))
(6 7 8 9 10)
 

Стоит заметить ограничения реализации: в качетсве функции возможна только унарная функция. Однако, этого нам будет вполне достаточно.

А также, функцию append~, которая реализует обединения двух списков, т.е. повдение вида:
 
(append~ '(a b c) '(c d e)) => (a b c c d e)
(append~ '(a b c) nil) => (a b c)
(append~ nil '(a b c)) => (a b c)
 

Реализация:
 
(defun append~ (x y)
(cond ((null x) y)
(t (cons (car x) (append~ (cdr x) y)))))
 

Тестирование:
 
> (append~ '(a b c) '(c d e))
(A B C C D E)
> (append~ 'nil'(c d e))
(C D E)
> (append~ '(a b c) nil)
(A B C)
 

Теперь перейдем к реализации целевой функции:
 
(defun all-subset~ (set)
(cond
((null set) '(nil))
(t (append~ (mapcar~ #'(lambda (x) (cons (car set) x))
(all-subset~ (cdr set)))
(all-subset~ (cdr set)))
)
)
)
 

Тестирование:
 
> (all-subset~ '(a))
((A) NIL)
> (all-subset~ '(a b))
((A B) (A) (B) NIL)
> (all-subset~ '(a b c))
((A B C) (A B) (A C) (A) (B C) (B) (C) NIL)
 
[1] > 2 < [3] [4] [5] [6] [7]


Онлайн :

0 пользователь(ей), 60 гость(ей) :




Реклама на сайте: