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

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

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) виводить необхідні номери елементів.