Power Set
পাওয়ার সেট
একটা set-এর সব উপসেটের set। `|𝒫(A)| = 2^|A|` — আর এই exponential বৃদ্ধিই brute force-এর সীমা টানে।
also: powerset
A = {1,2,3} হলে:
𝒫(A) = { ∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }আটটা = 2³।
Bitmask — power set-এর যান্ত্রিক রূপ:
def power_set(items):
n = len(items)
for mask in range(1 << n):
yield [items[i] for i in range(n) if mask >> i & 1]প্রতিটা mask একটা উপসেট; bit i সেট মানে items[i] আছে।
Exponential বিস্ফোরণ:
n | 2ⁿ |
|---|---|
| 20 | ১০ লক্ষ |
| 30 | ১০০ কোটি |
| 60 | 10¹⁸ — অসম্ভব |
তাই subset enumeration n ≈ 30 পর্যন্ত চলে, তার বেশি নয় —
আর এই সীমাটাই bitmask DP, truth table, আর NFA-থেকে-DFA
powerset construction — সবখানে একই।
|𝒫(𝒫(A))| = 2^(2^n) — n = 4-এ ৬৫,৫৩৬; n = 5-এ ৪২৯ কোটি।
এটাই n variable-এর সম্ভাব্য boolean function সংখ্যা।