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

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

Определения:
Прямым декартовым произведением множеств A1,...,An называется множество A1 x ... x An = {<a1,...,an> | a1A1,...,anAn}.

Перейдем к анализу задачи. Будем рассматривать только декартового произведение двух множеств. Это сужает произвольное количество множеств усложняет задачу, но не принципиально. Договоримся о представлении. Несмотря на то, что множество и упорядоченная пара – сущности разные ( хотя с помощью множеств легко моделировать упорядоченные пары) упорядоченные представлять будем в
виде списков. Для простоты также ограничимся множествами, элементы которых представляются атомами.

Прямая реализация – лаконично породить перебор всех вариантов. И сделать это с можно с помощью вложенных mapcar~. Однако, mapcar~ свормирует список не совсем той структцы, которая требуется. Рассмотрим промежуточное решение
 
(defun cartesian-product (a b)
(mapcar~ #'(lambda (x) (mapcar~ #'(lambda (y) (list x y))
b))
a
)
)
 

Тестирование:
 
> (cartesian-product '(a b) '(c d))
(((A C) (A D)) ((B C) (B D)))
 

В такой ситуации можно воспользоваться функцией apply. Напомним, что функция apply имеет следующий синтаксис
 
apply function arg &rest more-arg
 

и применяет функцию function к списку аргументов.

Таким образом:
 
> (apply #'append~ (cartesian-product '(a b) '(c d)))
((A C) (A D) (B C) (B D))
 


Мы получаем требуемый результат. Однако, пример существенно завязан на том, что у append~ два аргумента. Чтобы снять это ограничение можно воспользоваться либо встроенной функцией append, либо расширить реализацию append~ на произвольное количество аргументов. Сделать это можно следующим образом:
 
(defun append-no-limit (&rest c)
(cond ((null c) nil)
((null (cdr c)) (car c))
(t (eval (cons 'append-no-limit
(cons (list 'quote (append~ (car c) (cadr c)))
(mapcar~ #'(lambda (x) (list 'quote x))(cddr c))))))
)
)
 

Хотя, конечно, так лучше не делать :)

Тестирование:
 
> (append-no-limit '(a b c) '(c d e) '(e f g))
(A B C C D E E F G)
> (append-no-limit '(a b c) '(c d e) '(e f g) '(r t y))
(A B C C D E E F G R T Y)
 

Окончательное решение выглядит следующим образом:
 
(defun cartesian-product (a b)
(apply #'append-no-limit
(mapcar~ #'(lambda (x) (mapcar~ #'(lambda (y) (list x y))
b))
a
))
)
 

Тестируем:
 
> (cartesian-product '(1 2 3) '(1 2 3))
((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))
 
[1] [2] [3] > 4 < [5] [6] [7]


Онлайн :

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




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