Шаг 74.
Множества

    На этом шаге мы рассмотрим работу со множествами.

    Предметная область, задачи которой естественно формулируются в терминах работы с множествами, оказывается довольно широкой. Это неудивительно, так как язык теории множеств является универсальным языком математики.

    Тип данных "множество" не типичен для языков программирования. Это понятие привычно скорее для математиков, чем для программистов. Тем не менее выясняется, что для ряда приложений множества являются естественными объектами. Надо, конечно, понимать, что множества - объект идеальный, и фактически любой компьютер работает с "множеством" как с упорядоченным набором данных. Это, однако, еще не причина для того, чтобы заставлять и программиста работать с упорядоченными объектами: пусть язык даст ему возможность оперировать множествами.

    На этом шаге списки рассматриваются как множества своих элементов - порядку элементов в списке не придается значения, а два или более одинаковых элемента списка рассматриваются как один элемент множества.

    Пример 1. Библиотека функций для работы с множествами. 
   (DEFUN LIST-SET (LAMBDA (LST)
   ; Функция LIST-SET преобразует список LST в множество ;
      (COND ( (NULL LST) NIL )
            ( (MEMBER (CAR LST) (CDR LST))
                (LIST-SET (CDR LST)) )
            (  T  (CONS (CAR LST) (LIST-SET (CDR LST))) )
      )
   ))
   ; --------------------- ;
   (DEFUN SETP (LAMBDA (LST)
   ; Предикат SETР проверяет, является ли список LST ;
   ; множеством, т.е. входит ли каждый элемент LST в ;
   ;              список лишь один раз               ;
      (COND ( (NULL LST)                    T  )
            ( (MEMBER (CAR LST) (CDR LST)) NIL )
            (  T  (SETP (CDR LST)) )
      )
   ))
   ; ---------------------------- ;
   (DEFUN UNION (LAMBDA (LST1 LST2)
   ; Функция UNION возвращает объединение ;
   ;          множеств LST1 и LST2        ;
      (COND ( (NULL LST1) LST2 )
            ( (MEMBER (CAR LST1) LST2)
                (UNION (CDR LST1) LST2) )
            (  T  (CONS (CAR LST1) (UNION (CDR LST1) LST2)) )
      )
   ))
   ; ----------------------------------- ;
   (DEFUN INTERSECTION (LAMBDA (LST1 LST2)
   ; Функция INTERSECTION возвращает пересечение ;
   ;            множеств LST1 и LST2             ;
      (COND ( (NULL LST1) NIL )
            ( (MEMBER (CAR LST1) LST2)
                (CONS (CAR LST1)
                      (INTERSECTION (CDR LST1) LST2)) )
            (  T  (INTERSECTION (CDR LST1) LST2) )
      )
   ))
   ; ----------------------------- ;
   (DEFUN DIFFER (LAMBDA (LST1 LST2)
   ; Функцию DIFFER возвращает разность множеств LST1 и ;
   ; LST2, т.е. удаляет из множества LST1 все общие  с  ;
   ; множеством LST2 элементы                           ;
      (COND ( (NULL LST1) NIL  )
            ( (NULL LST2) LST1 )
            ( (MEMBER (CAR LST1) LST2)
                (DIFFER (CDR LST1) LST2) )
            (  T  (CONS (CAR LST1)
                        (DIFFER (CDR LST1) LST2)) )
      )
   ))
   ; --------------------------------- ;
   (DEFUN SYMDIFFER1 (LAMBDA (LST1 LST2)
   ; Функция SYMDIFFER1 возвращает симметрическую    ;
   ; разность множеств LST1 и LST2 (множество, со-   ;
   ; стоящее из всех элементов множеств LST1 и LST2, ;
   ; которые принадлежат или LST1, или LST2, но не   ;
   ; пересечению LST1 и LST2                         ;
      (COND ( (NULL LST1) LST2 )
            ( (MEMBER (CAR LST1) LST2)
                (SYMDIFFER1 (CDR LST1)
                            (REMOVE (CAR LST1) LST2)) )
            (  T  (CONS (CAR LST1)
                        (SYMDIFFER1 (CDR LST1) LST2)) )
      )
   ))
   ; --------------------------------- ;
   (DEFUN SYMDIFFER2 (LAMBDA (LST1 LST2)
   ; Функция SYMDIFFER2 возвращает симметрическую    ;
   ; разность множеств LST1 и LST2 (множество, со-   ;
   ; стоящее из всех элементов множеств LST1 и LST2, ;
   ; которые принадлежат или LST1, или LST2, но не   ;
   ; пересечению LST1 и LST2                         ;
      (COND ( (NULL LST1) LST2 )
            (  T  (DIFFER (UNION LST1 LST2)
                          (INTERSECTION LST1 LST2)) )
      )
   ))
   ; -------------------------------- ;
   (DEFUN EQUALSET1 (LAMBDA (LST1 LST2)
   ; Предикат EQUALSET1 проверяет равенство двух ;
   ; множеств LST1 и LST2                        ;
      (COND ( (NULL LST1) (NULL LST2) )
            ( (MEMBER (CAR LST1) LST2)
                    (EQUALSET1 (CDR LST1)
                               (REMOVE (CAR LST1) LST2)) )
            ( T  NIL )
      )
   ))
   ; -------------------------------- ;
   (DEFUN EQUALSET2 (LAMBDA (LST1 LST2)
   ; Предикат EQUALSET2 проверяет равенство двух ;
   ; множеств LST1 и LST2                        ;
      (AND (SUBSET LST1 LST2) (SUBSET LST2 LST1))
   ))
   ; ----------------------------- ;
   (DEFUN SUBSET (LAMBDA (LST1 LST2)
   ; Предикат SUBSET проверяет, является ли множество LST1 ;
   ; подмножеством множества LST2, иначе говоря, он  воз-  ;
   ; вращает  значение T, если каждый элемент списка LST1  ;
   ; содержится в списке LST2                              ;
      (COND ( (NULL LST2) (NULL LST1) )
            ( (NULL LST1) T )
            ( (MEMBER (CAR LST1) LST2)
                 (SUBSET (CDR LST1) LST2) )
            ( T  NIL )
      )
   ))
   ; ----------------------------------- ;
   (DEFUN NONINTERSECT (LAMBDA (LST1 LST2)
   ; Предикат NONINTERSECT проверяет, что множества ;
   ; LST1 и LST2 не пересекаются                    ;
      (COND ( (NULL LST1) T )
            ( (MEMBER (CAR LST1) LST2) NIL )
            (  T  (NONINTERSECT (CDR LST1) LST2) )
      )
   ))
   ; --------------------------- ;
   (DEFUN REMOVE (LAMBDA (ATM LST)
   ; Функция REMOVE возвращает список, в котором удалены ;
   ;      все вхождения элемента ATM в список LST        ;
      (COND ( (NULL LST) NIL )
            ( (EQ ATM (CAR LST)) (REMOVE ATM (CDR LST)) )
            (  T  (CONS (CAR LST) (REMOVE ATM (CDR LST))) )
      )
   ))
Текст этой библиотеки можно взять здесь.

    Пример 2. Функция возвращает список из общих символов (не только букв!) двух строк. 
   (DEFUN COMMON-LETTER (LAMBDA (W1 W2)
   ; W1 и W2 - литеральные атомы (слова)  ;
      (LIST-SET (INTERSECTION (UNPACK W1) (UNPACK W2)))
   ))
   ; ------------------------- ;
   (DEFUN LIST-SET (LAMBDA (LST)
   ; Функция LIST-SET преобразует список LST в множество ;
      (COND ( (NULL LST) NIL )
            ( (MEMBER (CAR LST) (CDR LST))
                (LIST-SET (CDR LST)) )
            (  T  (CONS (CAR LST) (LIST-SET (CDR LST))) )
      )
   ))
   ; ----------------------------------- ;
   (DEFUN INTERSECTION (LAMBDA (LST1 LST2)
   ; Функция INTERSECTION возвращает пересечение ;
   ;             множеств LST1 и LST2            ;
      (COND ( (NULL LST1) NIL )
            ( (MEMBER (CAR LST1) LST2)
                (CONS (CAR LST1)
                      (INTERSECTION (CDR LST1) LST2)) )
            (  T  (INTERSECTION (CDR LST1) LST2) )
      )
   ))
Текст этой функции можно взять здесь.

    Пример 3. Рассмотрим задачу генерации всех возможных перестановок множества из N элементов. (Предполагается, что множество задано в виде списка попарно различных элементов.)

    Пусть имеется программа, которая может генерировать список всех перестановок множества из (N-1) элементов. Тогда, чтобы построить все перестановки множества из N элементов, надо последовательно выбирать один из элементов этого множества и добавлять его на первое место в каждую из перестановок множества из (N-1) элементов, полученного из исходного множества удалением выбранного элемента. По нашему предположению, программа, генерирующая все перестановки множества из (N-1) элементов, уже существует. К этому следует добавить программу, генерирующую все перестановки пустого множества. Это легко сделать. Результатом работы этой программы должен быть список, состоящий из одного элемента - пустого множества.

    Правило генерации перестановок можно записать так.

    Пусть M - множество, состоящее из попарно различных элементов, все перестановки которого нужно построить. Тогда [1, с.56-57]: 

   < Все перестановки множества M > ::=
    если M - пустое множество, то (NIL),
    иначе
       для всех X, принадлежащих M,
         Объединить
            (Добавить X на первое место в каждой из
               < Все перестановки множества M без элемента X >)

    Приведем функции, необходимые для решения задачи: 

   (DEFUN PERMLIST (LAMBDA (M)
   ; Генерация всех перестановок элементов списка M ;
      (COND ( (NULL M) (LIST NIL) )
            (  T  (PERM2 M M) )
      )
   ))
   ; --------------------------- ;
   (DEFUN PERM2 (LAMBDA (UNUSED M)
   ; "Для всех X, принадлежащих M, объединить ..." ;
      (COND ( (NULL UNUSED) NIL )
            (  T  (APPEND (MULTICONS
                            (CAR UNUSED)
                            (PERMLIST (DELETE (CAR UNUSED) M)))
                         (PERM2 (CDR UNUSED) M)
                )
            )
      )
   ))
   ; ------------------------------ ;
   (DEFUN MULTICONS (LAMBDA (X LISTS)
   ; Добавление элемента X к каждому списку ;
   ; из списка LISTS                        ;
      (COND ( (NULL LISTS) NIL )
            (  T  (CONS (CONS X (CAR LISTS))
                        (MULTICONS X (CDR LISTS))) )
      )
   ))
   ; ----------------------- ;
   (DEFUN APPEND (LAMBDA (U V)
   ; Слияние двух списков U и V ;
      (COND ( (NULL U) V )
            (  T  (CONS (CAR U) (APPEND (CDR U) V)) )
      )
   ))
   ; ----------------------- ;
   (DEFUN DELETE (LAMBDA (X U)
   ; Удаление первого вхождения элемента X из списка U ;
   ;            на самом верхнем уровне                ;
      (COND ( (NULL U) NIL )
            ( (EQ (CAR U) X) (CDR U) )
            (  T  (CONS (CAR U) (DELETE X (CDR U))) )
      )
   ))
Текст этих функций можно взять здесь.

(1)Крюков А.П., Радионов А.Я., Таранов А.Ю., Шаблыгин Е.М. Программирование на языке R-Лисп. - М.: Радио и связь, 1991. - 192 с.

    Со следующего шага мы начнем знакомиться с бинарными деревьями поиска.




Предыдущий шаг Содержание Следующий шаг