Породження комбінаторних об’єктів, Детальна інформація

Реферат на тему:

Породження комбінаторних об’єктів.

Розглянемо задачі, в яких необхідно отримати всі елементи деякої множини.

1. Надрукувати всі послідовності довжини n з цифр 0,1. (P11 n).

Функція P11 викликається з одним аргументом n, аргумент lst – допоміжний.

(DEFUN p11 (n lst) (DEFUN p13 (n lst)

((ZEROP n) (PRIN1 lst) (TERPRI)) ((ZEROP n) (PRN13 lst) (TERPRI))

(P11 (- n 1) (CONS 0 lst)) (P13 (- n 1) (CONS 0 lst))

(P11 (- n 1) (CONS 1 lst)) ) (P13 (- n 1) (CONS 1 lst)) )

2. Надрукувати всі послідовності довжини k з чисел 1..n. (P12 k n).

Друкуватимемо послідовності у лексикографічному порядку. За допомогою функції (GEN1 n) згенеруємо список з n елементів, кожен з яких дорівнює 1. Список lst зберігатиме поточну перестановку. Функція (NEXT lst n) знаходить перестановку, яка буде наступною після lst. Функція P12BEST є найкращим рекурсивним розв’язком цієї задачі.

(DEFUN GEN1 n) (DEFUN NEXT (lst n)

((ZEROP n) NIL) ((< (CAR lst) n) (CONS (+ (CAR lst) 1) (CDR lst)))

(CONS 1 (GEN1 (- n 1))) ) ((NULL (CDR lst)) NIL)

(CONS 1 (NEXT (CDR lst) n))

Шукана функція має вигляд: (DEFUN P12BEST (n k lst c)

(DEFUN P12 k n) ((ZEROP n) (PRIN1 lst) (TERPRI))

(SETQ lst (GEN1 k)) (PUSH 1 c)

(LOOP (LOOP

((< (LENGTH lst) k)) ((> (CAR c) k))

(PRIN1 lst) (TERPRI) (P12BEST (- n 1) k (CONS (CAR c) lst) c)

(SETQ lst (NEXT lst n)) (SETQ c (CONS (+ 1 (CAR c)) (CDR c)))

) ) ) (POP c) )

3. Надрукувати всі підмножини множини {1..n}. (P13 n).

Оскільки всі підмножини будь-якої множини {1..n} перебувають у взаємно однозначній відповідності зі всіма послідовностями з 0 та 1 довжини n, то ця задача зводиться до задачі 1.1. Функція (P13 n) наведена в 1.1. Тільки замість виведення списку з 0 та 1 необхідно виводити номери всіх елементів списку, які дорівнюють 1. Функція (PRN13 lst) виводить необхідні номери елементів.

(DEFUN PRN13 (lst)

(SETQ i 0)

(LOOP

((NULL lst))

(INCQ i)