Tuesday, November 19, 2019

Էսսե տեղադրությունների մասին

— Ուսուցի՛չ,— ասաց Ուաո Գոն,— ինչպե՞ս կարելի է գեներացնել տողի բոլոր տեղադրությունները (permutations):

Կոնֆուցիոսը մի քիչ մտածեց ու հիշեց, որ այդ մասին կարդացել է Կնուտի «Ծրագրավորման արվեսստը» գրքի չորրորդ հատորում (Donald Knuth, «The Art of Computer Programming», vol. 4A)։ Այդ գրքի 7.2.1.2 Generating all permutations բաժնում պատմվում է տեղադրությունները գեներացնելու զանազան ալգորիթմների մասին. ինչպես միշտ՝ Կնուտն իր բարձունքի վրա է։

— Չգիտեմ։ Կարդացեք դասականներին,— ասաց Կոնֆուցիոսը մի քիչ էլ մտածելուց հետո։

* * *

Հաջորդ օրը Կոնֆուցիոսը տաճար մտավ ու տեսավ Ուաո Գոին աղոթելիս։ Կանչեց նրան իր սեղանի մոտ ու ցույց տվեց տախտակների վրա գրված այս տեքստը.

(defun insert-at (e l i)
    (if (zerop i)
        (cons e l)
        (cons (car l) (insert-at e (cdr l) (1- i)))))

(defun range (e r)
    (if (= 0 e)
        (cons 0 r)
        (range (1- e) (cons e r))))
(defun insert-at-all (e l)
    (mapcar #'(lambda (i) (insert-at e l i))
        (range (length l) '())))

(defun insert-to-all-items (e ls)
    (apply #'append (mapcar #'(lambda (q) (insert-at-all e q)) ls)))

(defun permutations-of (l)
    (if (null (cdr l))
        (list l)
        (insert-to-all-items (car l) (permutations-of (cdr l)))))

— Ի՞նչ է սա, ուսուցի՛չ,— հարցրեց Ուաո Գոն։

permutations-of-string-ը գեներացնում է տրված տողի բոլոր տեղադրությունները։

— Ինչպե՞ս։

— Տե՛ս։ Մի որևէ հաջորդականության բոլոր տեղադրությունները ստանալու համար կարելի է առանձնացնել դրա տարրերից մեկը, օրինակ առաջինը, ապա, ռեկուրսիվ եղանակով, հաշվել մյուս տարրերի հաջորդականության բոլոր տեղադրությունները և վերջում առանձնացված տարրը «խցկել» կառուցված տեղադրությունների բոլոր հնարավոր դիրքերում՝ ամեն մի «խցկելու» գործողությամբ գեներացնելով նոր տեղադրություն։ Պա՞րզ է։

— Լավ կլիներ օրինակ բերեիք, ուսուցի՛չ։

— Լավ։ Վերցնենք {a, b, c}։ Առաձնացնենք դրա առաջին տարրը՝ a-ն, մնացած տարրերի հաջորդականությունը կլինի {b, c}: Այս վերջինիս բոլոր հնարավոր տեղադրություններն են.

{(b, c), (c, b)}

Հիմա առանձնացված a տարրը տեղադրենք այս բազմության բոլոր տարրերի բոլոր դիրքերում։ (b, c)-ի համար կստանանք.

(a, b, c), (b, a, c), (b, c, a)

իսկ (c, b)-ի համար էլ.

(a, c, b), (c, a, b), (c, b, a)

Ահա սրանց միավորումն էլ հենց {a, b, c} հաջորդականության բոլոր տեղադրություններն են.

{(a, b, c), (b, a, c), (b, c, a), (a, c, b), (c, a, b), (c, b, a)}

— Ուսուցի՛չ, ո՞րն է ռեկուրսիայի տարրական դեպքը։

— Դա միայն մեկ տարր ունեցող հաջորդականությունն է։ Օրինակ, {a}-ի բոլոր տեղադրությունների բազմությունն է. {(a)}։

— Իսկ ի՞նչ հեզվով են գրված ձեր տախտակները, ուսուցի՛չ։

— Օ՜, դա Լիսպն է, լեզուների մեջ վեհագույնը։

— Թույլ տվեք մի անգամ էլ նայել տախտակներին,— խնդրեց Ուաո Գոն։

— Ահա՛։

— Թարգմանեք, խնդրում եմ, շատ հետաքրքիր է։

— Լավ։ Սկսենք առաջին տախտակից՝ ամենապարզից։ Ինչպես տեսար, տեղադրություններ կառուցելու տարրական գործողությունը տրված հաորդականության տրված դիրքում մի որևէ տարր խցկելն է։ Օրինակ, եթե հաջորդականությունն ունի երեք տարր՝ abc, ապա գոյություն ունեն նոր տարրը խցկելու 4 հնարավոր դիրքեր՝ ₀a₁b₂c₃։ insert-at գործողությունը e տարրը տեղադրում է l ցուցակի i-րդ դիրքում։

(defun insert-at (e l i)
    (if (zerop i)
        (cons e l)
        (cons (car l) (insert-at e (cdr l) (1- i)))))

Հաջորդ տախտակի վրա գրված insert-at-all գործողությունը e տարրը խցկում է l ցուցակի բոլոր թույլատրելի դիրքերում (դրանք |l|+1 հատ են), և վերադարձնում է խցկելու յուրաքանչյուր գործողությունից «ծնված» ցուցակների ցուցակը։ range օժանդակ ֆունկցիան պարզապես կառուցում է տարրը տեղադրելու ինդեքսների ցուցակը։

(defun range (e r)
    (if (= 0 e)
        (cons 0 r)
        (range (1- e) (cons e r))))
(defun insert-at-all (e l)
    (mapcar #'(lambda (i) (insert-at e l i))
        (range (length l) '())))

Երրորդ տախտակի insert-to-all-items գործողությունը insert-at-all ֆունկցիան կիրառում է ls ցուցակի բոլոր տարրերի նկատմամբ, և այդ կիրառություններից ստացված բոլոր ցուցակները միավորում է մի ընդհանուրի մեջ։

(defun insert-to-all-items (e ls)
    (apply #'append (mapcar #'(lambda (q) (insert-at-all e q)) ls)))

Դե, իսկ չորրորդ տախտակին գրված permutations-of գործողությունը հենց խնդրի բուն լուծումն է՝ ռեկուրսիայի կազմակերպմամբ։ Եթե տրված l ցուցակը միայն մի տարր ունի, ապա պատասխանը հենց այդ ցուցակը պարունակող ցուցակն է։ Ռեկուրսիայի քայլում կառուցվում է ցուցակի պոչի տեղադրությունների բազմությունը, ապա՝ insert-to-all-items նախնական ցուցակի առաջին տարրը ավելացվում է բոլոր այդ տեղադրություններին։

(defun permutations-of (l)
    (if (null (cdr l))
        (list l)
        (insert-to-all-items (car l) (permutations-of (cdr l)))))

— Իսկ ինչպե՞ս ենք կառուցելու _տողի_ բոլոր տեղադրությունների բազմությունը, ուսուցի՛չ։

— Դրա համար պետք է տողից կառուցենք նրա տառերի ցուցակը, կառուցենք այդ ցուցակի բոլոր տեղադրությունների բազմությունը, ապա ամեն մի տեղադրությունից ստանանք նոր տող։ Տո՛ւր ինձ մի մաքուր տախտակ։

Կոնֆուցիոսը վերցրեց Ուաո Գոի մեկնած տախտակն ու դրա վրա գրեց.

(defun permutations-of-string (s)
    (mapcar #'(lambda (e) (format nil "~(~{~C~}~)" e))
            (permutations-of (coerce s 'list))))

— Հիմա, Ուաո Գո՛, գնա ու շարունակիր աղոթքդ,— ասաց Կոնֆուցիոսը։

Ուաո Գոն խոնարհվեց ուսոցչին ու խնդրեց.

— Թույլ տուր մի անգամ էլ նայեմ տախտակներին։