แบ่งกลุ่ม

ปุจฉา : ถ้ามีคนอยู่ n คน เราจะสามารถแบ่งกลุ่มคนเหล่านี้ได้กี่แบบ โดยแต่ละกลุ่มมีคนได้อย่างน้อย 1 คน แบ่งแล้วมีกี่กลุ่มก็ได้ และไม่มีชื่อกลุ่ม
ให้คิดทั้ง กรณีที่ถือว่าทุกคนต่างกันหมด และ กรณีที่ถือว่าทุกคนเหมือนกัน

เรื่องมีอยู่ว่า
ผมอยากจะเขียนโปรแกรมที่ แก้ปัญหา แนวเกม 24 กรณ๊ทั่วไปได้
คือ ให้เลขมา n ตัว ให้หาวิธีบวกลบคูณทุกแบบ ที่ได้ เลข x ที่กำหนดไว้
ผมเขียนได้แล้ว
โดยใช้แนวคิดที่ว่า เลือกจับทีละคู่ แล้วลองบวกลบคูณหาร เอาผลลัพธ์ไปเป็น choice ในการจับคู่ต่อไป
ถ้ามี 4 ตัว ก็ทำ 3 ครั้งก้จะได้ ผลลัพธ์สุดท้าย ลองให้ครบทุกแบบ ก็จะได้ทุกวิธี
ผลออกมาก็คือ โปรแกรมนี้เป็น O(n^3*6^n) ครับ (ที่จริงคิดว่าทำให้เป็น n^2*6^n ได้ แต่ขี้เกียจ)
แถมยังนับ (1+3)+2 กับ 1+(3+2) เป็นคนละวิธี
ผมก็เลยคิดจะเขียนโปรแกรมใหม่ ที่มีคำนึงสมบัติการจัดหมู่

โปรแกรมแบบใหม่ที่คิดก็เลย ต้องแก้ปัญหาที่ข้างต้น ปุจฉาไว้ (จริงหรือ?)
ตอนที่ถามนั้น ผมคิดว่าผมเองคิดได้แล้วครับ เลยมาถาม
คิดมานานทีเดียวครับ และภุมิใจด้วยที่คิดออก
แต่ไม่ได้ prove วิธีของตัวเอง
กะว่า จะเล่าถึงศิลปะในการค้นหาวิธีการแก้ปัญหาเหล่านี้
ตอนนั้นหาใน net ก็ไม่เจอใครคิดมาก่อนก็แอบลุ้นว่า นี่ตูคิดคนแรกเชียวรึเปล่า (ก็งงว่า ปัญหาธรรมดาขนาดนี้ จะไม่มีคนคิดมาแล้วรึนี้ โอ้ เรานี่โชคดี ดีจังนะ)

บทสรุปก็คือ
หลังจากคุยกับอาจารย์มะนาว ก็พบว่า คิดผิดครับ เพราะ เค้ามีกันอยู่แล้ว โดยใช้วิธีที่มีประสิทธิภาพกว่าผมอีกด้วย
(อย่างไรก็ตาม วิธีที่ผมคิด ยังสามารถแก้ กรณีถือว่าทุกคนเหมือนกันหมดได้ แม้ประสิทธิภาพจะแย่กว่าอยู่ดี)
ไม่เป็นไรครับ
ยังไงก็ตาม อยากจะบอกว่า ได้ประโยชน์มาก จากการเดินทางตามหาความรู้รอบนี้
ได้เรียนรู้เรื่อง generating function และ เพิ่มศิลปะการแก้ปัญหาอีกนิด

ผมยัง ห่วยเรื่องการหาข้อมูลใน net มาเสมอ และต่อไปก็ต้อง หัดพิสูจน์ก่อนจะมั่นใจซะบ้าง
และตอนนี้ก็ยัง ไม่ได้เขียน โปรแกรม เกม 24 ที่ว่านั้นเลย ฮา.. หมดพลัง

http://mathworld.wolfram.com/BellNumber.html — กรณ๊ต่างกัน
http://en.wikipedia.org/wiki/Partition_function_(number_theory) –กรณีเหมือนกัน

ปล. อยากหาคนที่ชอบแนวนี้ มาคุยด้วยจัง เบื่อ ไม่มีเพื่อนอุดมการณ์เดียวกันเลย
ปล2. การจะทำเพลงในคอม นี้มันยากทีเดียวเน่อะครับ

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s