Sets — সব data structure-এর পূর্বপুরুষ

আগে এটা বুঝি

আপনি প্রতিদিন set ব্যবহার করেন — শুধু নাম ধরে ডাকেন না।

unique_visitors = set(log_entries)
active_users = registered & logged_in_today
banned = all_users - allowed

SELECT id FROM a UNION SELECT id FROM b;
SELECT id FROM a WHERE id IN (SELECT id FROM b);

permissions |= WRITE;          /* union */
if (flags & EXECUTE) { ... }   /* intersection non-empty? */

তিনটা ভিন্ন প্রযুক্তি — Python, SQL, C bitmask — কিন্তু তিনটাতেই একই তিনটা operation: union, intersection, difference।

কাকতালীয় নয়। এরা সবাই একই গাণিতিক কাঠামোর বাস্তবায়ন, আর সেই কাঠামোর নিয়মগুলো জানলে তিন জায়গাতেই একই যুক্তি খাটবে।

আর আরো গভীর একটা যোগ আছে: গত তিনটা লেসনে যে logic শিখলাম, set theory তার যমজ। ∧ আর ∩, ∨ আর ∪, ¬ আর complement — একই বীজগণিত, শুধু অন্য পোশাকে।

মূল ধারণা

Set কী

Set হলো স্বতন্ত্র বস্তুর একটা অসজ্জিত সংগ্রহ।

দুইটা শব্দ গুরুত্বপূর্ণ:

স্বতন্ত্র — একই জিনিস দুইবার থাকে না
অসজ্জিত — ক্রমের কোনো অর্থ নেই

{1, 2, 3} = {3, 1, 2} = {1, 1, 2, 3, 3}

তিনটাই একই set।

Programming-এ এটা ঠিক এভাবেই

>>> {1, 2, 3} == {3, 1, 2}
True
>>> {1, 1, 2, 3, 3}
{1, 2, 3}
>>> [1, 2, 3] == [3, 1, 2]
False          # list ক্রম-সংবেদী

এই কারণেই set আর list আলাদা type — গাণিতিকভাবেই এরা ভিন্ন বস্তু।

লেখার দুই উপায়

Roster notation — সদস্য গুনে গুনে:

A = {2, 3, 5, 7, 11}

Set-builder notation — শর্ত দিয়ে:

A = { x ∈ ℕ : x \< 12 এবং x মৌলিক }

দ্বিতীয়টা predicate logic-এরই আরেকটা চেহারা — : -এর ডানে যা আছে সেটাই predicate। আর এটা হুবহু list comprehension:

A = { x for x in range(12) if is_prime(x) }

গাণিতিক সংকেত আর Python syntax-এর মিলটা কাকতালীয় নয় — comprehension syntax সরাসরি set-builder notation থেকে ধার করা।

সদস্যপদ ও উপসেট

x ∈ A       x, A-এর সদস্য
A ⊆ B       A-এর প্রতিটা সদস্য B-তেও আছে      (subset)
A ⊂ B       A ⊆ B এবং A ≠ B                   (proper subset)

Formally: $A \subseteq B \iff \forall x\,(x \in A \to x \in B)$

লক্ষ্য করুন → ব্যবহার হয়েছে — গত লেসনের নিয়ম মনে আছে? ∀ চায় →।

আর দুইটা set সমান হয় যখন: $A = B \iff (A \subseteq B) \wedge (B \subseteq A)$

এটাই set সমতা প্রমাণের প্রামাণ্য পদ্ধতি — দুই দিকে subset দেখানো।

মৌলিক operation

Operation	সংকেত	সংজ্ঞা	Logic-এ সমতুল্য
Union	`A ∪ B`	`{x : x ∈ A ∨ x ∈ B}`	`∨`
Intersection	`A ∩ B`	`{x : x ∈ A ∧ x ∈ B}`	`∧`
Difference	`A \ B`	`{x : x ∈ A ∧ x ∉ B}`	`∧ ¬`
Complement	`A'` বা `Ā`	`{x ∈ U : x ∉ A}`	`¬`
Symmetric difference	`A △ B`	`(A\B) ∪ (B\A)`	`⊕` (XOR)

শেষ কলামটা লক্ষ্য করুন। প্রতিটা set operation একটা logical connective-এর প্রতিরূপ। এটাই duality।

Complement-এর জন্য universe লাগে

A' লিখতে হলে আগে বলতে হবে “কীসের মধ্যে”। Universal set U ছাড়া complement অর্থহীন।

Programming-এ এই সমস্যাটা বাস্তব: Python-এ set-এর complement method নেই, কারণ universe অজানা। C bitmask-এ আছে (~flags), কারণ সেখানে universe নির্দিষ্ট — সব bit position।

>>> ~{1,2,3}          # TypeError — অর্থহীন
>>> universe = set(range(10))
>>> universe - {1,2,3}
{0, 4, 5, 6, 7, 8, 9}

Set algebra — logic-এর যমজ

গত লেসনের প্রতিটা logical নিয়মের একটা set-রূপ আছে:

A ∪ B = B ∪ A                          commutative
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)        distributive
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)        distributive (দ্বৈত)

(A ∪ B)' = A' ∩ B'                     De Morgan
(A ∩ B)' = A' ∪ B'                     De Morgan

A ∪ (A ∩ B) = A                        absorption
A ∩ (A ∪ B) = A                        absorption

A ∪ ∅ = A          A ∩ U = A           identity
A ∪ U = U          A ∩ ∅ = ∅           domination
A ∪ A' = U         A ∩ A' = ∅          complement

একটাও নতুন করে মুখস্থ করার দরকার নেই। ∧ → ∩, ∨ → ∪, ¬ → ', T → U, F → ∅ — অনুবাদ করলেই হয়ে যায়।

একটা প্রমাণ করে দেখি

দাবি: (A ∪ B)' = A' ∩ B'

প্রমাণ (element chasing). যেকোনো x নিন।

\begin{aligned} x \in (A \cup B)' &\iff x \notin (A \cup B) &&\text{[complement-এর সংজ্ঞা]}\\ &\iff \neg(x \in A \vee x \in B) &&\text{[union-এর সংজ্ঞা]}\\ &\iff \neg(x \in A) \wedge \neg(x \in B) &&\text{[De Morgan — logic]}\\ &\iff x \in A' \wedge x \in B' &&\text{[complement]}\\ &\iff x \in A' \cap B' &&\text{[intersection]} \end{aligned}

প্রতিটা x-এর জন্য দুই পাশে সদস্যপদ সমতুল্য, তাই set দুটো সমান ∎

লক্ষ্য করুন তৃতীয় ধাপটা — সেখানে আমরা logic-এর De Morgan ব্যবহার করেছি। Set-এর De Morgan আসলে logic-এর De Morgan-এরই অনুবাদ।

ভেতরে কী ঘটছে

Cardinality — set-এর আকার

|A| = A-এর সদস্য সংখ্যা।

Inclusion–exclusion

দুইটা set-এর union-এ কতজন?

$|A \cup B| = |A| + |B| - |A \cap B|$

কেন বিয়োগ? কারণ যারা দুই set-এই আছে তাদের দুইবার গোনা হয়েছে।

তিনটার জন্য:

$|A \cup B \cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$

Pattern-টা লক্ষ্য করুন: বিজোড় সংখ্যক set-এর intersection যোগ, জোড় সংখ্যকগুলো বিয়োগ। সাধারণ রূপ:

$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\emptyset \ne S \subseteq \{1..n\}} (-1)^{|S|+1}\left|\bigcap_{i \in S} A_i\right|$

Power set — সব উপসেটের set

$\mathcal{P}(A) = \{ S : S \subseteq A \}$

A = {1, 2, 3} হলে:

𝒫(A) = { ∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }

আটটা। গত লেসনে আমরা induction দিয়ে প্রমাণ করেছি:

$|\mathcal{P}(A)| = 2^{|A|}$

Bitmask — power set-এর যান্ত্রিক রূপ

প্রমাণের সেই bit-string দৃষ্টিটা সরাসরি কোড হয়ে যায়:

def power_set(items):
    n = len(items)
    for mask in range(1 \<\< n):                    # 0 থেকে 2ⁿ−1
        yield [items[i] for i in range(n) if mask \>\> i & 1]

প্রতিটা mask একটা উপসেট। Bit i সেট মানে items[i] আছে।

একটা set operation কোথায় গিয়ে শেষ হয়

A ∩ Bগাণিতিক operation
a & b (Python set)hash table-এ দুই দিকে lookup
mask_a & mask_b (bitset)universe ছোট ও নির্দিষ্ট হলে
AND instructionএকটা machine instruction
64টা AND gate সমান্তরালেALU-র ভেতরে
দুইটা transistor সিরিজে × 64CMOS

Universe যদি ছোট আর নির্দিষ্ট হয় (যেমন ৬৪টা permission flag), তাহলে পুরো set operation-টা একটা CPU instruction-এ নেমে আসে। এই কারণেই bitset এত দ্রুত — Level 6-এ আমরা এটা measure করব।

Cartesian product

$A \times B = \{ (a, b) : a \in A,\; b \in B \}$

লক্ষ্য করুন এখানে ordered pair — ক্রম গুরুত্বপূর্ণ। (1, 2) ≠ (2, 1), যদিও {1, 2} = {2, 1}।

$|A \times B| = |A| \cdot |B|$

>>> from itertools import product
>>> list(product([1,2], ['a','b']))
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]

Cartesian product কেন গুরুত্বপূর্ণ:

Relation পরের লেসনের বিষয় — একটা relation হলো A × B-র একটা উপসেট
Database JOIN — cross join আক্ষরিকভাবে Cartesian product; অন্য সব join তার filtered রূপ
Type theory — tuple type (A, B) হলো A × B
State space — দুইটা স্বাধীন state variable-এর মিলিত state space তাদের product

Cartesian product দ্রুত বিস্ফোরিত হয়

SELECT * FROM a, b;      -- কোনো WHERE নেই

a-তে ১ লক্ষ row, b-তে ১ লক্ষ row → ১০ বিলিয়ন row।

এই একটা ভুল — join condition লিখতে ভুলে যাওয়া — production database বসিয়ে দেওয়ার সবচেয়ে সাধারণ উপায়।

অসীম set আর countability

সব অসীম সমান নয় — এটা Cantor-এর সবচেয়ে বিস্ময়কর আবিষ্কার।

একটা set countable যদি তার সদস্যদের 1, 2, 3, … দিয়ে গোনা যায় (অর্থাৎ ℕ-এর সাথে একের সাথে এক সঙ্গতি বসানো যায়)।

Set	Countable?
ℕ (স্বাভাবিক সংখ্যা)	✅
ℤ (পূর্ণসংখ্যা)	✅ `0, 1, −1, 2, −2, …`
ℚ (মূলদ সংখ্যা)	✅ (Cantor-এর কর্ণ গণনা)
সব সসীম দৈর্ঘ্যের string	✅
সব Python program	✅
ℝ (বাস্তব সংখ্যা)	❌
`𝒫(ℕ)`	❌
সব function ℕ → ℕ	❌

শেষ দুই সারির সংঘর্ষটা লক্ষ্য করুন:

Program-এর সংখ্যা countable, কিন্তু function-এর সংখ্যা uncountable।

অতএব অধিকাংশ function-ই কোনো program দিয়ে হিসাব করা যায় না।

এটা halting problem-এর চেয়েও মৌলিক একটা সীমা, আর এটা গোনার যুক্তি দিয়েই প্রমাণিত। Level 13-এ আমরা Cantor-এর diagonal argument পুরোটা করব এবং দেখব কীভাবে Turing হুবহু একই কৌশলে halting problem-এর অসমাধেয়তা প্রমাণ করেছিলেন।

উদাহরণ

Russell’s paradox — set theory ভেঙে পড়েছিল

উনিশ শতকের শেষে ধরে নেওয়া হতো: যেকোনো predicate P দিলেই একটা set বানানো যায় — {x : P(x)}। একে বলে unrestricted comprehension।

১৯০১-এ Bertrand Russell এই set-টা বিবেচনা করলেন:

$R = \{ x : x \notin x \}$

“যেসব set নিজেদের সদস্য নয়, তাদের set।”

এখন প্রশ্ন: R ∈ R?

যদি R ∈ R — তাহলে R-এর সংজ্ঞা অনুযায়ী R ∉ R। বিরোধ।
যদি R ∉ R — তাহলে R শর্ত মানে, তাই R ∈ R। বিরোধ।

দুইদিকেই বিরোধ। পুরো ভিত্তিটা ভেঙে পড়ল।

সমাধান: আধুনিক set theory (ZFC) unrestricted comprehension বাদ দিয়ে separation ব্যবহার করে — নতুন set শুধু একটা ইতিমধ্যে বিদ্যমান set থেকে বেছে নেওয়া যায়:

$\{ x \in A : P(x) \} \quad\text{বৈধ}$ $\{ x : P(x) \} \quad\text{অবৈধ}$

লক্ষ্য করুন — এটাই আপনার list comprehension-এর গঠন। Python-এ {x for x in A if P(x)} লিখতে হয়, {x if P(x)} নয়। ভাষার নকশাটাই paradox এড়ানোর নিয়ম মেনে চলে।

একই কাঠামো CS-এ বারবার ফিরে আসে

Russell’s paradox-এর গঠনটা হলো self-reference + negation। এই একই গঠন:

প্রসঙ্গ	রূপ
Liar paradox	“এই বাক্যটা মিথ্যা”
Russell	“নিজের সদস্য নয় এমন set-দের set”
Halting problem	“যে program থামে না তাকে থামায় এমন program”
Gödel	“এই বাক্যটা প্রমাণযোগ্য নয়”
Quine	নিজের source code ছাপায় এমন program

Level 13-এ আমরা দেখব এগুলো আসলে একই theorem-এর ভিন্ন প্রকাশ — Lawvere’s fixed-point theorem।

Set operation তিনভাবে — একই যুক্তি

একটা বাস্তব সমস্যা: “কোন user গতকাল active ছিল কিন্তু আজ না?”

Python set:

churned = active_yesterday - active_today

SQL:

SELECT user_id FROM active_yesterday
EXCEPT
SELECT user_id FROM active_today;

Bitmask (user id ছোট ও ঘন হলে):

uint64_t churned = yesterday & ~today;

তিনটাই A \ B = A ∩ B'। একই গাণিতিক পরিচয়, তিনটা বাস্তবায়ন।

কোনটা কখন:

	Python set	SQL	Bitmask
Universe	যেকোনো hashable	table	ছোট, ঘন পূর্ণসংখ্যা
Memory	~50 byte/element	disk page	1 bit/element
Difference	`O(	A	)`
কখন	সাধারণ ক্ষেত্রে	ডেটা ইতিমধ্যে DB-তে	id ঘন, লক্ষ লক্ষ

Bitmask-এর memory সুবিধাটা নাটকীয়: ১০ লক্ষ user-এর একটা set — Python-এ ~৫০ MB, bitset-এ ১২৫ KB। ৪০০ গুণ কম।

এই কারণেই Roaring Bitmap-এর মতো data structure আছে, যা Elasticsearch, Druid আর ClickHouse-এ ব্যবহার হয়। Level 8-এ আমরা এগুলো দেখব।

নিজে চালিয়ে দেখুন

EXPERIMENT

Set operation-এর তিনটা বাস্তবায়ন মেপে দেখুন

Python 3· ১৫ মিনিট

import sys, time, random

N = 1_000_000          # universe আকার
DENSITY = 0.5

ids_a = set(random.sample(range(N), int(N * DENSITY)))
ids_b = set(random.sample(range(N), int(N * DENSITY)))

# ── ১. Python set ─────────────────────────────────────────────
t0 = time.perf_counter()
diff_set = ids_a - ids_b
t_set = time.perf_counter() - t0
mem_set = sys.getsizeof(ids_a) + sys.getsizeof(ids_b)

# ── ২. Python int হিসেবে bitmask ──────────────────────────────
def to_bitmask(s):
    m = 0
    for x in s:
        m |= 1 \<\< x
    return m

mask_a, mask_b = to_bitmask(ids_a), to_bitmask(ids_b)
t0 = time.perf_counter()
diff_mask = mask_a & ~mask_b
t_mask = time.perf_counter() - t0
mem_mask = (mask_a.bit_length() + mask_b.bit_length()) // 8

print(f"universe = {N:,}, density = {DENSITY}")
print(f"\n{'':12} {'time':>12} {'memory':>14}")
print(f"{'set':12} {t_set*1000:>10.2f}ms {mem_set/1e6:>12.2f}MB")
print(f"{'bitmask':12} {t_mask*1000:>10.2f}ms {mem_mask/1e6:>12.2f}MB")
print(f"\nfaster: {t_set/t_mask:.1f}×   smaller: {mem_set/mem_mask:.1f}×")

# ফলাফল একই কি না যাচাই
assert bin(diff_mask).count('1') == len(diff_set)
print("\n✓ দুইটা পদ্ধতি একই উত্তর দিয়েছে")

সাধারণত bitmask ১০–৫০ গুণ দ্রুত আর ৩০–৫০ গুণ ছোট।

এবার density কমিয়ে দেখুন — DENSITY = 0.001 করুন:

universe = 1,000,000, density = 0.001
set          0.05ms       0.06MB
bitmask      0.12ms       0.25MB

ছবি উল্টে গেল! Sparse set-এ bitmask খারাপ, কারণ universe-এর প্রতিটা position-এর জন্য bit রাখতে হয় — সদস্য থাক বা না থাক।

এটাই মূল শিক্ষা: গাণিতিক operation একই, কিন্তু সঠিক বাস্তবায়ন নির্ভর করে ডেটার গঠনের উপর। Level 6-এ আমরা এই ধরনের সিদ্ধান্ত নিয়মতান্ত্রিকভাবে নিতে শিখব।

এটা কী প্রমাণ করে

একই গাণিতিক operation-এর বিভিন্ন বাস্তবায়নের খরচ নাটকীয়ভাবে আলাদা — আর কোনটা বাছবেন তা universe-এর গঠনের উপর নির্ভর করে, operation-এর উপর নয়।

EXPERIMENT

SQL-এ set operation আর NULL-এর ফাঁদ

PostgreSQL· ১০ মিনিট

CREATE TEMP TABLE a (x int);
CREATE TEMP TABLE b (x int);
INSERT INTO a VALUES (1), (2), (2), (3), (NULL);
INSERT INTO b VALUES (2), (3), (4), (NULL);

-- UNION duplicate সরায়, UNION ALL সরায় না
SELECT 'UNION'      AS op, count(*) FROM (SELECT x FROM a UNION     SELECT x FROM b) t
UNION ALL
SELECT 'UNION ALL',        count(*) FROM (SELECT x FROM a UNION ALL SELECT x FROM b) t
UNION ALL
SELECT 'INTERSECT',        count(*) FROM (SELECT x FROM a INTERSECT SELECT x FROM b) t
UNION ALL
SELECT 'EXCEPT',           count(*) FROM (SELECT x FROM a EXCEPT    SELECT x FROM b) t;

ফলাফল:

    op     | count
-----------+-------
 UNION     |     5     -- {1,2,3,4,NULL}
 UNION ALL |     9     -- সব row, duplicate সহ
 INTERSECT |     3     -- {2,3,NULL}  ← NULL মিলে গেল!
 EXCEPT    |     2     -- {1}         ← আরেকটা কী?

দুইটা বিস্ময়:

১. INTERSECT-এ NULL মিলে গেল। অথচ আগের লেসনে দেখেছি NULL = NULL → NULL, সত্য নয়!

কারণ: set operation = ব্যবহার করে না, ব্যবহার করে IS NOT DISTINCT FROM — যা NULL-কে NULL-এর সমান গণ্য করে। এটা ইচ্ছাকৃত, কারণ duplicate সরাতে হলে NULL-দেরও এক গণ্য করতে হয়।

২. তুলনা করুন NOT IN-এর সাথে:

SELECT count(*) FROM a WHERE x NOT IN (SELECT x FROM b);

 count
-------
     0     -- ⚠ শূন্য! অথচ EXCEPT দুইটা দিয়েছিল

কারণ b-তে একটা NULL আছে। x NOT IN (2,3,4,NULL) মানে x != 2 AND x != 3 AND x != 4 AND x != NULL। শেষ শর্তটা সবসময় NULL, তাই পুরো conjunction কখনো TRUE হয় না। সব row বাদ পড়ে।

এটা production-এ নীরবে ভুল ফল দেয়

NOT IN + nullable subquery = সবচেয়ে বিপজ্জনক SQL pattern-গুলোর একটা। কোনো error নেই, শুধু খালি ফলাফল।

নিরাপদ বিকল্প: NOT EXISTS বা EXCEPT ব্যবহার করুন।

-- নিরাপদ
SELECT * FROM a WHERE NOT EXISTS (SELECT 1 FROM b WHERE b.x = a.x);

এটা কী প্রমাণ করে

SQL-এর set operation গাণিতিক set-এর মতো আচরণ করে, কিন্তু NULL আর duplicate-এর ব্যাপারে সূক্ষ্ম পার্থক্য আছে যা ভুল ফল দেয়।

নিজে বানান

BUILD IT

তিনটা Set বাস্তবায়ন — একই interface

Python · ●●●○○

একটা abstract interface ঠিক করুন — add, contains, union, intersect, difference
List-ভিত্তিক (সরল, ধীর), hash-ভিত্তিক, আর bitmask-ভিত্তিক — তিনটা লিখুন
তিনটাই একই set algebra নিয়ম মানে কি না property-test করুন
Universe আকার আর density বদলে performance তুলনা করুন

from abc import ABC, abstractmethod

class SetABC(ABC):
    @abstractmethod
    def add(self, x): ...
    @abstractmethod
    def __contains__(self, x): ...
    @abstractmethod
    def __len__(self): ...
    @abstractmethod
    def union(self, other): ...
    @abstractmethod
    def intersect(self, other): ...
    @abstractmethod
    def difference(self, other): ...
    @abstractmethod
    def to_list(self): ...


# ── ১. List-ভিত্তিক — সরলতম, সবচেয়ে ধীর ───────────────────────
class ListSet(SetABC):
    def __init__(self, items=()):
        self.items = []
        for x in items: self.add(x)

    def add(self, x):
        if x not in self.items:          # O(n) — এখানেই খরচ
            self.items.append(x)

    def __contains__(self, x): return x in self.items
    def __len__(self):         return len(self.items)
    def to_list(self):         return sorted(self.items)

    def union(self, o):      return ListSet(self.items + o.items)
    def intersect(self, o):  return ListSet(x for x in self.items if x in o)
    def difference(self, o): return ListSet(x for x in self.items if x not in o)


# ── ২. Hash-ভিত্তিক — Python-এর নিজের set যা করে ───────────────
class HashSet(SetABC):
    """সরলীকৃত chaining hash set — Level 6-এ পুরোটা বানাব"""
    def __init__(self, items=(), buckets=64):
        self.buckets = [[] for _ in range(buckets)]
        self.n = 0
        for x in items: self.add(x)

    def _slot(self, x):
        return self.buckets[hash(x) % len(self.buckets)]

    def add(self, x):
        s = self._slot(x)
        if x not in s:
            s.append(x); self.n += 1

    def __contains__(self, x): return x in self._slot(x)
    def __len__(self):         return self.n
    def to_list(self):         return sorted(x for b in self.buckets for x in b)

    def union(self, o):      return HashSet(self.to_list() + o.to_list())
    def intersect(self, o):  return HashSet(x for x in self.to_list() if x in o)
    def difference(self, o): return HashSet(x for x in self.to_list() if x not in o)


# ── ৩. Bitmask — universe ছোট ও পূর্ণসংখ্যা হলে ────────────────
class BitSet(SetABC):
    def __init__(self, items=(), universe=1024):
        self.universe = universe
        self.mask = 0
        for x in items: self.add(x)

    def add(self, x):
        assert 0 <= x \< self.universe, f"{x} universe-এর বাইরে"
        self.mask |= 1 \<\< x

    def __contains__(self, x): return bool(self.mask \>\> x & 1)
    def __len__(self):         return bin(self.mask).count('1')
    def to_list(self):
        return [i for i in range(self.universe) if self.mask \>\> i & 1]

    def _wrap(self, m):
        r = BitSet(universe=self.universe); r.mask = m; return r

    def union(self, o):      return self._wrap(self.mask | o.mask)
    def intersect(self, o):  return self._wrap(self.mask & o.mask)
    def difference(self, o): return self._wrap(self.mask & ~o.mask)


# ── তিনটাই একই আইন মানে কি না যাচাই ────────────────────────────
import random

def check_laws(cls, trials=200, universe=64, **kw):
    for _ in range(trials):
        a = cls(random.sample(range(universe), 10), **kw)
        b = cls(random.sample(range(universe), 10), **kw)
        c = cls(random.sample(range(universe), 10), **kw)

        L = lambda s: s.to_list()

        # commutative
        assert L(a.union(b))     == L(b.union(a))
        assert L(a.intersect(b)) == L(b.intersect(a))

        # associative
        assert L(a.union(b).union(c)) == L(a.union(b.union(c)))

        # distributive:  a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c)
        assert L(a.intersect(b.union(c))) == L(a.intersect(b).union(a.intersect(c)))

        # absorption:  a ∪ (a ∩ b) = a
        assert L(a.union(a.intersect(b))) == L(a)

        # difference:  a \ b = a ∩ b'   (universe-এর মধ্যে)
        univ = cls(range(universe), **kw)
        assert L(a.difference(b)) == L(a.intersect(univ.difference(b)))

    print(f"✓ {cls.__name__} — সব set algebra আইন মানে")

check_laws(ListSet)
check_laws(HashSet)
check_laws(BitSet, universe=64)

তিনটা সম্পূর্ণ আলাদা বাস্তবায়ন — একটা list scan করে, একটা hash করে, একটা bit ঠেলে — তবু তিনটাই একই বীজগণিত মানে।

এটাই abstraction-এর মূল ধারণা: interface একই, implementation ভিন্ন, আর গাণিতিক নিয়ম সবার উপরে।

নিজে বাড়ান:

symmetric_difference যোগ করুন তিনটাতেই, আর যাচাই করুন A △ B = (A ∪ B) \ (A ∩ B)
তিনটার add আর contains -এর সময় measure করুন n = 10, 100, 1000, 10000-এ — কোনটা কোথায় ভাঙে?
BitSet-কে universe > 64 -এর জন্য word-array দিয়ে লিখুন (Python-এর বড় int-এর উপর নির্ভর না করে)
একটা SortedSet যোগ করুন যা binary search ব্যবহার করে — O(log n) contains কিন্তু O(n) add
hypothesis দিয়ে property-based test লিখুন যা তিনটা বাস্তবায়নকে Python-এর built-in set-এর সাথে তুলনা করে

বাস্তব সিস্টেমে

Set কোথায় কোথায়

Relational database। “Relational” শব্দটাই set theory থেকে। একটা table হলো tuple-এর একটা set, আর প্রতিটা query হলো set operation-এর একটা সমষ্টি। Codd-এর ১৯৭০-এর মূল পেপারটার নামই ছিল “A Relational Model of Data for Large Shared Data Banks” — আর সেখানে সব কিছু set algebra-য় সংজ্ঞায়িত।

Type system। Union type (string | number) হলো set union। Intersection type (A & B) হলো set intersection। Subtyping হলো subset সম্পর্ক। TypeScript-এর type checker আক্ষরিকভাবে set operation চালায়।

Access control। একজন user-এর কার্যকর permission = তার সব role-এর permission set-এর union, বিয়োগ explicit deny set। Kubernetes RBAC, AWS IAM — সবই এই হিসাব।

Compiler-এর dataflow analysis। “এই point-এ কোন variable গুলো live?” — উত্তরটা একটা set, আর সেটা হিসাব হয় set equation-এর fixed point বের করে:

LIVE_in[n]  = USE[n] ∪ (LIVE_out[n] \ DEF[n])
LIVE_out[n] = ⋃ LIVE_in[s]  for all successors s

Level 5-এ আমরা এটা implement করব।

Version control। Git-এর three-way merge মূলত set operation: কোন লাইন যোগ হয়েছে, কোনটা মুছেছে — দুই শাখায় — তার union আর intersection। Conflict হয় যখন intersection খালি নয়।

Search engine। একটা inverted index প্রতিটা শব্দের জন্য document id-র একটা set রাখে। "cat AND dog" মানে দুই set-এর intersection। Lucene/Elasticsearch এটা Roaring Bitmap দিয়ে করে — আমাদের bitmask experiment-এরই শিল্পস্তরের রূপ।

Garbage collection। Mark-and-sweep আক্ষরিকভাবে দুইটা set নিয়ে কাজ করে: reachable object-এর set (mark phase-এ বানানো), আর সব object-এর set। যা sweep হবে = difference। Level 5-এ দেখব।

যে ভুলগুলো সবাই করে

“Set আর list মূলত একই, set-এ শুধু duplicate থাকে না।”

পার্থক্য আরো গভীর — এরা ভিন্ন গাণিতিক বস্তু।

Set-এ ক্রমের কোনো অর্থ নেই। এর মানে হলো একটা set implementation সদস্যদের যেকোনো ক্রমে রাখতে পারে, আর সেই স্বাধীনতাই hash-ভিত্তিক O(1) lookup সম্ভব করে।

List-এ ক্রম অর্থবহ, তাই index দিয়ে access করা যায় — কিন্তু membership test O(n)।

>>> s = {1, 2, 3}
>>> s[0]                    # TypeError — set indexable নয়
>>> list({'b','a','c'})     # ক্রম নির্ভরযোগ্য নয়

Python-এ set iteration-এর ক্রম hash-এর উপর নির্ভর করে, আর string-এর জন্য সেটা প্রতি run-এ বদলায় (hash randomization, security feature)। সেই ক্রমের উপর নির্ভর করা bug।

সঠিক মানসিক মডেল: set = “কী আছে” (membership); list = “কী আছে এবং কোন ক্রমে” (sequence)। যদি ক্রম না লাগে, set নিন — তখন implementation দ্রুততর হতে পারে।

“খালি set আর {∅} একই জিনিস।”

সম্পূর্ণ আলাদা।

∅       — খালি set, |∅| = 0
{∅}     — একটা set যার ভেতরে একটা জিনিস আছে (সেই জিনিসটা খালি set),
          |{∅}| = 1

উপমা: ∅ একটা খালি বাক্স। {∅} একটা বাক্স যার ভেতরে একটা খালি বাক্স। দ্বিতীয়টা খালি নয়।

>>> len(set())
0
>>> len({frozenset()})
1

এই পার্থক্যটা তুচ্ছ মনে হলেও, von Neumann-এর সংখ্যা নির্মাণে এটাই ভিত্তি:

0 = ∅
1 = {∅}          = {0}
2 = {∅, {∅}}     = {0, 1}
3 = {0, 1, 2}

প্রতিটা সংখ্যা তার আগের সব সংখ্যার set। শূন্য থেকে গোটা arithmetic নির্মাণ করা যায় শুধু set দিয়ে।

প্রোগ্রামিং-এ সমতুল্য: null আর [null] এক নয়; "" আর [""] এক নয়; খালি response আর “একটা খালি object” এক নয়। API design-এ এই পার্থক্য না রাখলে ambiguity তৈরি হয়।

“A ⊆ B আর A ∈ B — প্রায় একই।”

একেবারেই না, আর এটা গুলিয়ে ফেললে গুরুতর ভুল হয়।

A = {1, 2}
B = {1, 2, 3}
C = {{1, 2}, 3}

A ⊆ B  ✓   A-এর প্রতিটা সদস্য B-তে আছে
A ∈ B  ✗   A নিজে B-এর সদস্য নয়
A ⊆ C  ✗   1 ∈ A কিন্তু 1 ∉ C
A ∈ C  ✓   A নিজেই C-এর একটা সদস্য

⊆ — “ভেতরের সব জিনিস ওখানে আছে” ∈ — “এই জিনিসটা ওখানে আছে”

Programming-এ:

a = {1, 2}
b = {1, 2, 3}
c = {frozenset({1,2}), 3}

a.issubset(b)      # True   — ⊆
a in b             # False  — ∈  (এবং TypeError-ও হতে পারে)
frozenset(a) in c  # True   — ∈

∅ ⊆ A সব A-এর জন্য সত্য (vacuously), কিন্তু ∅ ∈ A সাধারণত মিথ্যা। এই দুইটা গুলিয়ে ফেলা set theory-র প্রমাণে সবচেয়ে সাধারণ ভুল।

“অসীম set মানেই সব একই আকারের।”

Cantor প্রমাণ করেছেন এটা মিথ্যা — আর এটা গণিতের সবচেয়ে গভীর আবিষ্কারগুলোর একটা।

|ℕ| = |ℤ| = |ℚ| — তিনটাই countably infinite, একই আকার (যদিও ℚ কে “ঘন” মনে হয়)।

কিন্তু |ℝ| > |ℕ| — বাস্তব সংখ্যা কঠোরভাবে বেশি।

আর সাধারণভাবে: |𝒫(A)| > |A| সব set-এর জন্য, এমনকি অসীম set-এর জন্যও। অর্থাৎ অসীমেরও অসীম সোপান আছে।

CS-এর জন্য সবচেয়ে গুরুত্বপূর্ণ পরিণতিটা এই:

সব program-এর set        → countable  (প্রতিটা program একটা সসীম string)
সব function ℕ→ℕ -এর set  → uncountable

তাই প্রায় প্রতিটা function-ই uncomputable — কোনো program দিয়ে হিসাব করা যায় না।

এটা “আমরা এখনো algorithm খুঁজে পাইনি” নয়। এটা “algorithm নেই, থাকতে পারে না” — গোনার যুক্তি দিয়ে প্রমাণিত।

বুঝেছেন কি না দেখুন

প্রমাণ করুন A \ (B ∪ C) = (A \ B) ∩ (A \ C) — element chasing দিয়ে।

প্রয়োগ

যেকোনো x নিন:

\begin{aligned} x \in A \setminus (B \cup C) &\iff x \in A \wedge x \notin (B \cup C) \\ &\iff x \in A \wedge \neg(x \in B \vee x \in C) \\ &\iff x \in A \wedge (x \notin B \wedge x \notin C) &&\text{[De Morgan]}\\ &\iff (x \in A \wedge x \notin B) \wedge (x \in A \wedge x \notin C) &&\text{[idempotent + rearrange]}\\ &\iff x \in (A\setminus B) \wedge x \in (A \setminus C) \\ &\iff x \in (A\setminus B) \cap (A\setminus C) \end{aligned}

∎

চতুর্থ ধাপটা লক্ষ্য করুন — সেখানে x ∈ A কে দুইবার ব্যবহার করেছি। এটা বৈধ কারণ p ≡ p ∧ p (idempotent)।

যাচাই করুন কোডে:

A, B, C = {1,2,3,4}, {2,3}, {3,4}
assert A - (B | C) == (A - B) & (A - C)   # {1}

ব্যবহারিক তাৎপর্য: ডান পাশটা parallelize করা সহজ — A\B আর A\C আলাদা machine-এ হিসাব করে শেষে intersect করা যায়। বাঁ পাশে আগে B ∪ C বানাতে হয়, যা একটা sequential নির্ভরতা।

Distributed query engine (Spark, Presto) এই ধরনের rewriting করে ঠিক এই কারণে।

|A| = 4 হলে |𝒫(𝒫(A))| কত? উত্তর দেওয়ার আগে অনুমান করুন।

যুক্তি

$|\mathcal{P}(A)| = 2^4 = 16$ $|\mathcal{P}(\mathcal{P}(A))| = 2^{16} = 65{,}536$

এবং যদি আরেক স্তর নিতেন:

$|\mathcal{P}(\mathcal{P}(\mathcal{P}(A)))| = 2^{65536}$

এই সংখ্যাটার দশমিক অঙ্ক প্রায় ১৯,৭২৯টা। মহাবিশ্বে পরমাণুর সংখ্যা প্রায় 10^80 — অর্থাৎ ৮১ অঙ্কের। তুলনাই হয় না।

এই বিস্ফোরণটা CS-এ বারবার ফিরে আসে:

Subset enumeration O(2ⁿ) — n = 30 পর্যন্ত চলে, n = 60 কখনো না
Truth table n variable-এ 2ⁿ row — একই সীমা
Powerset construction — NFA থেকে DFA বানানোর সময় state সংখ্যা 2ⁿ হতে পারে (Level 13)
Boolean function n variable-এ 2^(2ⁿ) টা — দ্বৈত exponential

n = 5-এই boolean function-এর সংখ্যা 2^32 = ৪২৯ কোটি। n = 6-এ 2^64 = ১.৮ × ১০¹⁹।

তাই কোনো general-purpose “সব boolean function চেষ্টা করে দেখি” পদ্ধতি কাজ করবে না — আর এই কারণেই SAT solver-দের চতুর হতে হয়, brute force চলে না।

আপনার একটা feature-flag সিস্টেম আছে। প্রতিটা user-এর জন্য কার্যকর flag নির্ধারিত হয়: global defaults ∪ (user-এর plan-এর flags) ∪ (user-এর নিজস্ব overrides), বিয়োগ explicitly disabled flags।

এটাকে set operation-এ লিখুন, আর বলুন কোন ক্রমে evaluate করলে কী সমস্যা হতে পারে।

ডিজাইন

Formula:

$\text{effective} = \big(G \cup P \cup O\big) \setminus D$

যেখানে G = global, P = plan, O = override, D = disabled।

সমস্যা ১: D কোথায় প্রয়োগ হবে?

উপরের রূপে D সবার শেষে — অর্থাৎ disable সর্বোচ্চ অগ্রাধিকার, কোনো override সেটা ফেরাতে পারবে না।

বিকল্প নকশা:

$\text{effective} = \big((G \cup P) \setminus D\big) \cup O$

এখানে override disable-কেও হারায়। সম্পূর্ণ ভিন্ন আচরণ।

Set difference distributive নয় union-এর উপর সেভাবে: (A ∪ B) \ C = (A\C) ∪ (B\C) ✓ সত্য, কিন্তু (A \ C) ∪ B ≠ (A ∪ B) \ C যখন B ∩ C ≠ ∅।

তাই ক্রমটা নকশাগত সিদ্ধান্ত, আর সেটা স্পষ্ট করে লিখতেই হবে।

সমস্যা ২: “override” মানে কি শুধু enable?

বাস্তব সিস্টেমে override দুই দিকেই হয় — কেউ একটা flag জোর করে বন্ধও করতে চায়। তখন একটা set যথেষ্ট নয়, দরকার তিন-মানের mapping:

flag → { ON, OFF, UNSET }

তখন এটা আর set নয়, একটা partial function — পরের লেসনের বিষয়।

সমস্যা ৩: Precedence স্পষ্ট নয়।

P আর O-তে একই flag ভিন্ন মানে থাকলে কে জেতে? Union বলে না — union-এ দুটোই থাকে। তাই layered configuration-এ set ব্যবহার করলে precedence প্রকাশই করা যায় না।

সঠিক নকশা:

LAYERS = ['global', 'plan', 'user']     # ক্রম = precedence

def resolve(flag, layers):
    value = False
    for layer in LAYERS:                # পরেরটা আগেরটাকে ঢাকে
        if flag in layers[layer]:
            value = layers[layer][flag]
    return value

শিক্ষা: set একটা চমৎকার মডেল যখন প্রশ্নটা শুধু “আছে কি নেই”। যখনই “কোন মান” বা “কে জেতে” আসে, তখন set যথেষ্ট নয় — function বা partial order লাগে।

গাণিতিক মডেল ভুল বাছলে সেটা code-এ ambiguity হয়ে ফিরে আসে।

একটা ক্লাসে ৩০ জন। ১৮ জন Python জানে, ১৫ জন C জানে, ৮ জন দুটোই জানে। কতজন কোনোটাই জানে না?

প্রয়োগ

Inclusion–exclusion:

$|P \cup C| = |P| + |C| - |P \cap C| = 18 + 15 - 8 = 25$

কোনোটাই জানে না:

$30 - 25 = 5$

পাঁচজন।

যাচাই — Venn-এর অঞ্চল ধরে:

অঞ্চল	সংখ্যা
শুধু Python	`18 − 8 = 10`
শুধু C	`15 − 8 = 7`
দুটোই	`8`
কোনোটাই না	`5`
মোট	30 ✓

কেন 18 + 15 = 33 > 30 -তে ভয় পাওয়ার কিছু নেই: কারণ ৮ জনকে দুইবার গোনা হয়েছে। 33 − 8 = 25 — এটাই union।

CS-এ একই হিসাব:

Database query planner WHERE a = 1 OR b = 2 -এর selectivity অনুমান করতে ঠিক এই সূত্র ব্যবহার করে:

$s(A \vee B) = s(A) + s(B) - s(A) \cdot s(B)$

শেষ পদটা s(A ∧ B) -এর অনুমান, ধরে নেওয়া হয় A আর B স্বাধীন।

এই স্বাধীনতার অনুমানটাই প্রায়ই ভুল — যদি a আর b সম্পর্কিত হয় (যেমন city আর postcode), তাহলে estimate বহুগুণ ভুল হয়, আর planner খারাপ plan বেছে নেয়।

Level 8-এ আমরা দেখব PostgreSQL কীভাবে multivariate statistics দিয়ে এই সমস্যা কমানোর চেষ্টা করে।

কেন Python-এ set -এর সদস্য hashable হতে হয়, কিন্তু list -এর element-এর কোনো শর্ত নেই?

যুক্তি

কারণ set-এর মূল প্রতিশ্রুতি হলো O(1) membership test — আর সেটা hash table ছাড়া সম্ভব নয়।

Hash table কাজ করে এভাবে:

Element-এর hash বের করে
সেই hash থেকে একটা bucket index
সেই bucket-এ খোঁজে

এর জন্য দুইটা শর্ত:

(ক) Hash গণনাযোগ্য হতে হবে।

>>> hash([1,2,3])
TypeError: unhashable type: 'list'

(খ) Hash অপরিবর্তনীয় হতে হবে। এটাই আসল কারণ।

যদি mutable object set-এ রাখা যেত:

s = set()
lst = [1, 2]
s.add(lst)          # কল্পনা করুন এটা সম্ভব
lst.append(3)       # hash বদলে গেল!
lst in s            # False — অথচ ঠিক ওটাই তো রেখেছিলাম

Object-টা এখন ভুল bucket-এ পড়ে আছে। সেটা আর কখনো খুঁজে পাওয়া যাবে না, মুছেও ফেলা যাবে না। Set-এর invariant ভেঙে গেল।

তাই Python নিয়ম করেছে: hashable মানে immutable (বা অন্তত hash-এর দিক থেকে immutable)।

>>> {frozenset([1,2])}      # ✓ frozenset immutable
>>> {(1, 2)}                # ✓ tuple immutable
>>> {[1, 2]}                # ✗ TypeError
>>> {(1, [2])}              # ✗ tuple হলেও ভেতরে list আছে

List-এ এই সমস্যা নেই কারণ list element-দের hash করে না — শুধু ক্রমে রাখে। in operator O(n) linear scan করে, == দিয়ে তুলনা করে। তাই যেকোনো object চলে।

গাণিতিক দৃষ্টিতে: set-এর সংজ্ঞায় সদস্যপদ (x ∈ A) একটা স্থির সত্য — সময়ের সাথে বদলায় না। Mutable object সেই স্থিরতা ভাঙে। Python-এর hashability নিয়মটা আসলে গাণিতিক সংজ্ঞাটাই enforce করছে।

Level 6-এ আমরা hash table নিজে বানাব আর এই invariant-গুলো হাতে-কলমে দেখব।

এরপর কী

Set আমাদের দিয়েছে “কী আছে” বলার ভাষা। কিন্তু বেশিরভাগ আকর্ষণীয় প্রশ্ন জিনিসগুলোর মধ্যকার সম্পর্ক নিয়ে।

কে কার বন্ধু? কোন module কোন module-এর উপর নির্ভর করে? কোন task কোন task-এর আগে চলতে হবে? কোন state থেকে কোন state-এ যাওয়া যায়?

পরের লেসনে আসছে relations — আর সেটা A × B-র উপসেট হিসেবে সংজ্ঞায়িত, অর্থাৎ আজকের Cartesian product-এর সরাসরি সম্প্রসারণ।

সেখান থেকে আসবে equivalence relation (যা জিনিসকে শ্রেণিতে ভাগ করে), partial order (যা dependency আর scheduling-এর ভিত্তি), আর topological sort — যা এই ওয়েবসাইটের কারিকুলাম roadmap-টাই বানিয়েছে।

Sets — সব data structure-এর পূর্বপুরুষ

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

Set কী

লেখার দুই উপায়

সদস্যপদ ও উপসেট

মৌলিক operation

Set algebra — logic-এর যমজ

একটা প্রমাণ করে দেখি

ভেতরে কী ঘটছে

Cardinality — set-এর আকার

Inclusion–exclusion

Power set — সব উপসেটের set

Bitmask — power set-এর যান্ত্রিক রূপ

Cartesian product

অসীম set আর countability

উদাহরণ

Russell’s paradox — set theory ভেঙে পড়েছিল

একই কাঠামো CS-এ বারবার ফিরে আসে

Set operation তিনভাবে — একই যুক্তি

নিজে চালিয়ে দেখুন

Set operation-এর তিনটা বাস্তবায়ন মেপে দেখুন

SQL-এ set operation আর NULL-এর ফাঁদ

নিজে বানান

তিনটা Set বাস্তবায়ন — একই interface

বাস্তব সিস্টেমে

Set কোথায় কোথায়

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

Set কী

লেখার দুই উপায়

সদস্যপদ ও উপসেট

মৌলিক operation

Set algebra — logic-এর যমজ

একটা প্রমাণ করে দেখি

⚙ভেতরে কী ঘটছেUnder the hood

Cardinality — set-এর আকার

Inclusion–exclusion

Power set — সব উপসেটের set

Bitmask — power set-এর যান্ত্রিক রূপ

Cartesian product

অসীম set আর countability

▶উদাহরণExample

Russell’s paradox — set theory ভেঙে পড়েছিল

একই কাঠামো CS-এ বারবার ফিরে আসে

Set operation তিনভাবে — একই যুক্তি

⌘নিজে চালিয়ে দেখুনExperiment

Set operation-এর তিনটা বাস্তবায়ন মেপে দেখুন

SQL-এ set operation আর NULL-এর ফাঁদ

⚒নিজে বানানBuild it yourself

তিনটা Set বাস্তবায়ন — একই interface

◉বাস্তব সিস্টেমেReal-world usage

Set কোথায় কোথায়

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী