Monthly Archives: August 2014

มีความพยายามแต่ยังอ่อนหัด (แก้โจทย์ clojure)

ช่วงนี้กลับมาเล่น 4clojure อีกครั้งจากที่ทิ้งไปเป็นปี หลังจากรวบรวมพลังแก้ข้อที่ติดมานานไปได้ วันนี้มีเรื่องสนุกๆ เกี่ยวกับข้อล่าสุดที่เพิ่งแก้ไปมาให้ฟัง (มีการเฉลยวิธีการแก้ ถ้าอยากเล่นเองไม่ควรอ่าน)

โจทย์ของข้อนี้ คือ ให้หา Power Set ของ set ที่ให้มา

พอเห็นโจทย์แล้วก็คิดว่าน่าจะไม่อยาก expand ด้วย map ซักที concat ซักทีน่าจะได้แล้ว แต่ทำไม่ออกแหะ
วิธีการถึกๆ อันนึงที่คิดออกคือ หา Permutation ของ element ใน set ต้ังแต่ permutation ของ 0 ตัวถึง n ตัว แล้วมาจับยัดใส่ set มันก็กำจัด duplicate ให้เราเอง

ปัญหาคือเขียน Permutation ไม่เป็นครับ ความรู้ algorithm เข้ากรุไปหมดแล้ว ทำ depth-first search, breath-first search ด้วย recursive ยังไงหว่า เอ๊ะแล้วถ้าไม่ทำ recursive แต่ใช้พวก map แทนจะทำได้มั้ยหว่า ขีดๆเขียนๆบนกระดาษอยู่นานก็ไม่ออกซักที เลยเริ่มจะโกงด้วยการไปแอบดูวิธีการทำ permutation จาก library ซะ เออมันก็ดูง่ายนะ ไล่ๆ ไปเรื่อยถึงฟังก์ชันที่เป็น core ของการทำงานนี้ งงครับ มีโคตรให้ดูรันดูผลลัพธ์ได้ยังงง เลยเริ่มท้อไม่ทำ permutation แม่งละ

คิดไปคิดมาได้ไอเดียใหม่ ถ้าเราทำการหาเลขฐาน 2 ตั้งแต่ 0 ถึงจำนวนหลักเท่ากับจำนวน element ใน set แปลง set ของเราเป็น vector (array) แล้วเอาเลขฐาน 2 แต่ละอันนั้นมาเทียบดู ถ้าเลขฐาน 2 ที่ตำแหน่งใดๆเป็น 1 เราก็ดึง element จาก vector ที่ index นั้นออกมา ถ้าเป็น 0 เราก็ไม่เอา จับมายัดใส่ set ก็จะได้ Power set แล้วนี่หว่า
ตัวอย่าง 00, 01, 10, 11 กับ #{ 1, 2 } -> #{}, #{ 2 }, #{ 1 }, #{ 1, 2 }
วิธีนี้เป็นการโกงไม่ต้อง expand เอง ใช้คุณสมบัติของเลขฐาน 2 ทำให้ 😀 ก็เขียนโค้ดออกมาซะ

(fn [input]
 (letfn [(binary->subset [aset binary]
           (let [v (into [] aset)]
             (->> binary 
               (map-indexed vector)
               (map #(when (not= \0 (last %)) (nth v (first %)))) ;; ดึง element ออกจาก set ถ้าเป็นเลข 1
               (remove nil?)
               (into #{}))))
         (gen-binary [n] 
            (->> n
              (Math/pow 2)
              (range)
              (map #(Integer/toString % 2)) ;; สร้างเลขฐาน 2
              (map #(clojure.pprint/cl-format nil (str "~" n ",'0d") %)))) ;; เติม 0 ข้างหน้า
         (power-set [aset]
           (->> aset
             (count)
             (gen-binary) ;; สร้างเลขฐาน 2 ทั้งหมด
             (map #(binary->subset aset %)) ;; เทียบเลขฐาน 2 กัน set
             (into #{})))]
   (power-set input)))

code นี้ก็ถูกต้อง แก้โจทย์ผ่านมาได้สบายใจ แต่ 4clojure มีข้อดีอย่างหนึ่งคือเมื่อเราแก้โจทย์ข้อไหนผ่านแล้ว เราจะมีสิทธิ์ดูวิธีการแก้ปัญหาของคนอื่นได้ แล้วผมก็พบคนนึงที่แก้ด้วย code ชุดนี้

(partial reduce 
  #(into % (map (fn[s](conj s %2)) %)) 
  #{#{}})

ร้องไห้แป๊ป ทำไมมันง่ายได้ขนาดนี้ เค้าใช้วิธีการดึง element ของ set ออกมาทีละตัว สร้างเป็น set แล้วก็ดึง element ถัดไปมาใส่ใน set ไปเรื่อยๆจนหมด
บน clojure ถ้าเราเปลี่ยน reduce เป็น reductions มันจะทำการ print แต่ละ step ของ reduce ออกมาแทน ซึ่งสำหรับ code ด้านบนนี้ได้ผลแบบนี้

;; power set ของ #{ 1 2 3 }
(#{#{}} ;; เริ่มด้วย set ว่าง
#{#{} #{1}} ;; ใส่ 1 เข้าไปในทุกๆเซ็ต และสร้างเซ็ตของ 1 เพิ่มด้วย
#{#{} #{3} #{1} #{1 3}} ;; ใส่ 3 เข้าไปในทุกๆเซ็ต และสร้างเซ็ตของ 3 เพิ่มด้วย
#{#{} #{3} #{2} #{1} #{1 3 2} #{1 3} #{1 2} #{3 2}}) ใส่ 2 เข้าไป

ยังมีชีวิตอยู่ก็เรียนรู้กันต่อไปครับ

Advertisements