เขียนหนึ่งเซตย่อยใน $\binom{n}{r}$ ด้วยความเร็ว $O(r\log n)$
ส่วนใหญ่เวลาเราคำนวณเกี่ยวกับการนับ เช่น $n!$ หรือ $\binom{n}{r}$ เรามักสนใจแค่ผลลัพธ์เชิงตัวเลขของมันว่าให้ค่าเป็นเท่าไหร่ อย่างเช่น $\binom{8}{3} = 56$ ที่ตีความได้ว่า เซตของสมาชิก $8$ ตัวเมื่อต้องการเลือกเซตย่อยที่มีสมาชิก $3$ ตัวจะสามารถทำได้ทั้งหมด $56$ วิธีไม่ซ้ำกัน
ว่าแต่ว่า แต่ละวิธีที่หยิบสมาชิกได้นั้นมันหยิบสมาชิกตัวไหนออกมาบ้างหละ? เพื่อให้เราไล่เขียนทุกวิธีได้อย่างมีระเบียบไม่ต้องสับสนกังวลว่าจะเขียนซ้ำ เราจะสนใจการไล่เขียนเรียงตามลำดับพจนานุกรม เช่น สมมติให้เซตของสมาชิกทั้ง $8$ ตัวนั้นคือตัวอักษรภาษาอังกฤษ $ABCDEFGH$ การไล่เขียนเซตย่อยของตัวอักษรมา $3$ ตัว วิธีแรกจะเขียนได้ว่า $ABC$ ตามด้วย $ABD$ ไล่ไปเรื่อยๆ จนจบที่ $FGH$ หรือไล่ให้ดูทั้งหมดได้ว่า
\[\begin{array}{c} ABC \quad ABD \quad ABE \quad ABF \quad ABG \quad ABH \\ ACD \quad ACE \quad ACF \quad ACG \quad ACH \\ ADE \quad ADF \quad ADG \quad ADH \\ AEF \quad AEG \quad AEH \\ AFG \quad AFH \\ AGH \\ BCD \quad BCE \quad BCF \quad BCG \quad BCH \\ BDE \quad BDF \quad BDG \quad BDH \\ BEF \quad BEG \quad BEH \\ BFG \quad BFH \\ BGH \\ CDE \quad CDF \quad CDG \quad CDH \\ CEF \quad CEG \quad CEH \\ CFG \quad CFH \\ CGH \\ DEF \quad DEG \quad DEH \\ DFG \quad DFH \\ DGH \\ EFG \quad EFH \\ EGH \\ FGH \end{array}\]จากตัวอย่างง่ายๆ ข้างต้น สังเกตว่ามีถึง $21$ วิธีที่เขียนขึ้นต้นด้วยตัว $A$ แต่หลังจากนั้นมีเพียงแค่ $15$ วิธีที่ขึ้นต้นด้วยตัว $B$ และลดหลั่นลงไปเรื่อยๆ จนถึงตัว $F$ ที่ขึ้นต้นได้แค่วิธีเดียว
อนึ่ง เราอาจมองภาพข้างต้นเป็นพีระมิดหัวกลับที่แบ่งเป็นชั้นๆ เมื่อเริ่มต้นด้วยตัวอักษรใหม่ก็ย่อมได้ ซึ่งเมื่อดูให้ลึกลงไป (no pun intended) จะเห็นว่าการขึ้นต้นด้วยตัว $A$ นั้นมีจำนวนวิธีเท่ากับ $\binom{8}{3}{-}\binom{7}{3}$ ซึ่งก็คือผลต่างของพีระมิดสองชั้นที่ติดกัน ทำให้ได้เป็นขนาดของชั้นหนึ่งๆ นั่นเอง
ยิ่งไปกว่านั้น เมื่อระลึกถึงสามเหลี่ยมปัสกาล เรายังได้อีกว่า $\binom{8}{3}{-}\binom{7}{3} = \binom{7}{2}$ หรือหากจะตีความหมายในที่นี้ก็คือ บังคับเลือกตัวอักษร $A$ ดังนั้นจะเหลือตัวอักษรอีก $7$ ตัวซึ่งเราต้องเลือกเพิ่มอีก $2$ ตัว และทำให้ได้ว่ามี $\binom{7}{2}$ วิธีที่ต้องเลือกตัวอักษร $A$ เป็นตัวแรกสุดนั่นเอง
เรายังใช้การวิเคราะห์ในทำนองเดียวกันกับตัวอักษรอื่นๆ ได้ เช่น $B$ ที่มีวิธีเลือก $\binom{7}{3}{-}\binom{6}{3}=\binom{6}{2}$ วิธี
จากข้อสังเกตข้างต้น จึงทำให้เราได้อัลกอริทึมที่ตรงไปตรงมาสำหรับเลือกเซตย่อย ณ ตำแหน่งที่ $i$ ตามลำดับพจนานุกรมดังนี้
from math import comb # comb(n, r) = n!/(r!(n-r)!)
def choose(n, r, i, x=0):
assert 0 <= i < comb(n, r)
if r == 0:
return []
if i >= comb(n-1, r-1):
j = i - comb(n-1, r-1)
return choose(n-1, r, j, x+1)
return [x] + choose(n-1, r-1, i, x+1)
น่าเสียดายที่อัลกอริทึมดังกล่าวทำงานที่ความเร็วแค่ $O(n)$ เพราะว่ามันอาจจะต้องเรียกตัวเองลึกลงไปจนถึงค่า $n$ ที่น้อยที่สุดจึงจะได้คำตอบ … แล้วเราทำดีกว่านี้ได้หรือเปล่า?
แน่นอนว่าเมื่อเจอปัญหาที่แบ่งเป็นชั้นๆ แบบนี้ เราควรจะลองค้นหาแบบทวิภาคดูซักหน่อย สังเกตว่าถ้าเราไม่หาขนาดของชั้นเพียงชั้นเดียวในพีระมิด แต่หาขนาดของหลายๆ ชั้นที่ติดกันไปเลย เราสามารถทำได้โดยเอาพีระมิดที่ใหญ่ที่สุดไปลบพิระมิดระหว่างทางได้ ดังนั้นเราอาจตัดจำนวนชั้นที่ไม่ใช่ไปได้ถึงครึ่งหนึ่ง ซึ่งนี่เป็นหัวใจสำคัญของการค้นหาทวิภาคนั่นเอง และมันก็ทำให้เราได้โค้ดนี้ออกมา
def binsearch(n, r, i, lo, hi):
if lo >= hi:
return lo
mid = (lo + hi) // 2
if i < comb(n, r) - comb(mid, r):
return binsearch(n, r, i, lo, mid)
else:
return binsearch(n, r, i, mid+1, hi)
def choose(n, r, i, x=0):
if r == 0:
return []
k = binsearch(n, r, i, lo=0, hi=n)
y = x + n - k
j = i - (comb(n, r) - comb(k, r))
return [y] + choose(k-1, r-1, j, y+1)
น่าเสียดายที่ยังไงเราก็ต้องค่อยๆ แกะสมาชิกตัวแรกในเซตย่อยที่เป็นคำตอบออกมาทีละตัว ซึ่งก็คือแม้เราจะใช้เวลาเพียง $O(\log n)$ ในการหาสมาชิกที่ถูกต้องตัวหนึ่งๆ แต่เราก็ยังต้องทำแบบเดียวกันกับสมาชิกให้ครบ $r$ ตัวอยู่ดี ดังนั้นจึงได้เวลารวมเป็น $O(r \log n)$
แล้ว $O(r \log n)$ มันดีกว่า $O(n)$ หรือเปล่า? ถ้า $r \to n$ หละก็ไม่ดีแน่ๆ แต่ในโลกจริงแล้วเรามักจะสนใจกรณีที่ $r \ll n$ เสียเป็นส่วนใหญ่ นอกจากนี้หาก $r >n/2$ เราก็สามารถใช้เทคนิคการสลับด้านสามเหลี่ยมปัสกาลได้ ซึ่งก็คือจะเห็นได้ไม่ยากว่า
set(range(n)) == set(choose(n, r, i) + choose(n, n-r, comb(n,r)-1-i))
author