Permutation আর combination তৈরি — lexicographic order আর backtracking

১ · গোনা থেকে তৈরি করা — কেন সব বস্তু একে একে বানাতে হয়

আগের কয়েকটি পর্বে প্রশ্ন ছিল “কয়টি?”. পর্ব ৩৩ “Permutation আর combination”-এ জেনেছেন ৪টি পণ্য একটি তাকে 4! = 24 ভাবে সাজানো যায়, আর পর্ব ৩৫-এ জেনেছেন ৪ ফ্লেভার থেকে ৬ প্যাকেটের ঝুড়ি ৮৪টি। কিন্তু কাল্পনিক অনলাইন দোকান বাজারঘরের প্রকৌশলীদের প্রায়ই সংখ্যা যথেষ্ট নয়, তাঁদের দরকার বস্তুগুলো নিজেই:

• একজন রাইডার ৬টি ঠিকানায় যাবেন; সবচেয়ে ছোট পথ খুঁজতে সব 6! = 720টি ক্রম একে একে পরীক্ষা করতে হবে।
• ১০টি পণ্যের মধ্যে কোন ৩টি একসঙ্গে “কম্বো অফার” হবে, তা ঠিক করতে C(10, 3) = 120টি দল একে একে দেখতে হবে।
• নতুন sort ফাংশন পরীক্ষার জন্য ৭টি সংখ্যার সব 5040টি ক্রম ইনপুট হিসেবে চালাতে হবে।
• লটারির মতো এলোমেলোভাবে ক্রেতাদের সারি সাজাতে হবে, যাতে প্রতিটি ক্রম সমান সম্ভাব্য হয়।

একটি ভালো generator-এর কাছে আমরা তিনটি জিনিস চাই। সম্পূর্ণতা: প্রতিটি বস্তু অন্তত একবার আসে। পুনরাবৃত্তিহীনতা: কোনো বস্তু দুবার আসে না। এই দুটি মিলে বলে, generator-এর তালিকা আর বস্তুর সেটের মধ্যে একটি bijection আছে (পর্ব ১৬), তাই তালিকার দৈর্ঘ্য গোনার সূত্রের সঙ্গে মিলতে বাধ্য: এটিই আমাদের প্রথম পরীক্ষা। দক্ষতা: এক বস্তু থেকে পরেরটিতে যেতে অল্প কাজ, আদর্শভাবে গড়ে ধ্রুবক।

ক্রম হিসেবে সবচেয়ে স্বাভাবিক হলো অভিধানের ক্রম, যাকে বলে lexicographic order: দুটি তালিকার প্রথম যে ঘরে পার্থক্য, সেখানে যার মান ছোট, সে আগে। যেমন 1 3 2 আসে 2 1 3-এর আগে, কারণ প্রথম ঘরেই 1 < 2. অভিধানে “কলম” আগে, “কলা” পরে নয়, একই নিয়মে। এই পর্বের মূল কাজ: lexicographic ক্রমে একটি বস্তু দেওয়া থাকলে ঠিক পরেরটি বের করা, আর প্রমাণ করা যে সেটিই পরেরটি।

২ · সব subset — binary counting

সবচেয়ে সহজ উদাহরণ দিয়ে শুরু। S = {চা, ডাল, তেল}-এর সব subset তৈরি করতে চাই, যাদের সংখ্যা 2³ = 8 (পর্ব ১৪-এর power set). প্রতিটি subset-কে তিন বিটের একটি bit string দিয়ে লিখুন: প্রথম বিট 1 মানে চা আছে, দ্বিতীয় বিট ডাল, তৃতীয় বিট তেল. যেমন 101 = {চা, তেল}. এখন 0 থেকে 7 পর্যন্ত সাধারণ গোনা, binary-তে 000, 001, 010, 011, 100, 101, 110, 111, ঠিক একবার করে প্রতিটি subset দেয়।

প্রমাণ:

1. 0 ≤ k ≤ 2ⁿ − 1-এর প্রতিটি সংখ্যার ঠিক একটি n-বিট binary রূপ আছে (শুরুতে দরকারমতো 0 বসিয়ে)। — স্থানীয় মানের সংখ্যা পদ্ধতি
2. n-বিট string আর S-এর subset-এর মধ্যে “বিট 1 মানে উপাদানটি আছে” একটি bijection, যার উল্টো ফাংশন subset থেকে প্রতিটি বিট পড়ে নেয়। — পর্ব ১৪
3. দুটি bijection-এর composition bijection. ∎ — পর্ব ১৬

এই কৌশলের একটি দুর্বলতা আছে। 011 থেকে 100-এ যেতে তিনটি বিটই বদলায়: ঝুড়ি থেকে ডাল আর তেল সরিয়ে চা ঢোকাতে হয়। যদি প্রতিটি subset-এর জন্য কোনো খরচসাপেক্ষ হিসাব থাকে (যেমন ঝুড়ির মোট ওজন), তাহলে পরপর দুটি subset যত কাছাকাছি, হিসাব হালনাগাদ তত সস্তা। একটি করে বিট বদলিয়ে সব subset ঘুরে আসা যায় কি? উত্তর হ্যাঁ, আর সেটিই পরের অংশের বিষয়।

৩ · Gray code — প্রতি ধাপে মাত্র একটি বিট

সব n-বিট string-এর এমন একটি তালিকা, যেখানে পরপর দুটির মধ্যে ঠিক একটি বিট আলাদা, তাকে বলে Gray code. দুটি string কয়টি ঘরে আলাদা, সেই সংখ্যাকে বলে Hamming distance; তাই Gray code-এ পরপর দুটি string-এর Hamming distance 1. সবচেয়ে পরিচিত নির্মাণটি “প্রতিফলন” দিয়ে, তাই নাম reflected Gray code:

এভাবে G(2) = 00, 01, 11, 10 আর G(3) = 000, 001, 011, 010, 110, 111, 101, 100. নিচের stepper নির্মাণটি ধাপে ধাপে দেখায়।

1G(1) = 0, 12G(2) = 0·G(1), 1·G(1)ᴿ3G(3) প্রথম অর্ধেক: 0·G(2)4G(3) দ্বিতীয় অর্ধেক: 1·G(2)ᴿ5যাচাই: সংযোগ, আবর্তন, সূত্র

প্রমাণ (n-এর ওপর mathematical induction, পর্ব ১০):

1. ভিত্তি n = 1: G(1) = 0, 1. দুটি শব্দই আছে, একবার করে, আর 0 ↔ 1 এক বিটের বদল। — সরাসরি পরীক্ষা
2. অনুমান: G(n)-এর জন্য তিনটি দাবিই সত্য। ধরুন G(n)-এর প্রথম শব্দ f আর শেষ শব্দ ℓ. — inductive hypothesis
3. সম্পূর্ণতা: 0·G(n)-এ শুরুতে 0 আছে এমন সব 2ⁿটি শব্দ একবার করে, 1·G(n)^R-এ শুরুতে 1 আছে এমন সব; দুই অর্ধেকের শব্দ প্রথম বিটেই আলাদা। মোট 2ⁿ⁺¹, পুনরাবৃত্তিহীন। — অনুমান + যোগের নিয়ম
4. অর্ধেকের ভেতরে: 0·G(n)-এ পরপর দুটি শব্দ 0w আর 0w′, যেখানে w, w′ G(n)-এ পরপর, তাই এক বিটে আলাদা। উল্টো ক্রমেও পাশাপাশি থাকা জোড়া একই থাকে, তাই 1·G(n)^R-এও একই কথা। — অনুমান
5. সংযোগস্থল: প্রথম অর্ধেক শেষ হয় 0ℓ দিয়ে, দ্বিতীয় অর্ধেক শুরু হয় 1ℓ দিয়ে (প্রতিফলনে ℓ প্রথমে আসে)। পার্থক্য শুধু প্রথম বিটে। — নির্মাণ
6. আবর্তন: G(n + 1) শুরু হয় 0f দিয়ে আর শেষ হয় 1f দিয়ে (প্রতিফলনে f শেষে যায়); পার্থক্য শুধু প্রথম বিটে। ∎ — নির্মাণ

ছবিটি একটি সুন্দর সমতুল্যতা দেখায়: n-বিট string-গুলোকে কোণ ধরে, এক বিটে আলাদা কোণ যুক্ত করলে যে গ্রাফ পাওয়া যায় তার নাম n-মাত্রার hypercube Q_n, আর একটি চক্রাকার Gray code মানে Q_n-এর একটি Hamiltonian cycle, অর্থাৎ প্রতিটি কোণ ঠিক একবার ছুঁয়ে ফেরার পথ। উপপাদ্য ৩.২ তাই প্রমাণ করে, প্রতিটি n ≥ 2-এর জন্য Q_n-এ Hamiltonian cycle আছে। গ্রাফের এই ভাষা মডিউল ১০-এর গ্রাফ তত্ত্বে আরও আসবে।

Reflected Gray code-এর একটি সরাসরি সূত্রও আছে: G(n)-এর k-তম শব্দ (০ থেকে গুনে) হলো k ⊕ (k ≫ 1), অর্থাৎ k-এর binary রূপের সঙ্গে এক ঘর ডানে সরানো k-এর বিটওয়াইজ XOR. Hardware-এ এই রূপান্তর এবং তার উল্টোটি Computer Architecture কোর্সের পর্ব ৪-এ আছে; এখানে আমরা সূত্রটি প্রমাণের বদলে Python-এ বড় n পর্যন্ত মিলিয়ে দেখব (অনুশীলন ১-এ এর একটি ফল প্রমাণ করবেন)। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

def gray(n):
    """reflected Gray code: G(n+1) = 0 G(n), then 1 G(n) reversed"""
    codes = [""]
    for _ in range(n):
        codes = ["0" + c for c in codes] + ["1" + c for c in reversed(codes)]
    return codes

def diff(a, b):                       # Hamming distance
    return sum(x != y for x, y in zip(a, b))

print("G(3):", " ".join(gray(3)))
for n in range(1, 13):
    g = gray(n)
    one_bit = all(diff(g[k], g[(k + 1) % len(g)]) == 1 for k in range(len(g)))
    distinct = len(set(g)) == 2 ** n
    formula = all(int(g[k], 2) == k ^ (k >> 1) for k in range(len(g)))
    if n in (1, 2, 3, 4, 8, 12):
        print(f"n = {n:2}: {len(g):4} words, cyclic one-bit: {one_bit},"
              f" all distinct: {distinct}, k xor (k>>1): {formula}")

items = ["cha", "dal", "tel"]         # a 3-item shop shelf
prev = "000"
for code in gray(3)[1:]:
    k = next(i for i in range(3) if code[i] != prev[i])
    move = "add" if code[k] == "1" else "remove"
    basket = [items[i] for i in range(3) if code[i] == "1"]
    print(code, f"{move:6} {items[k]:3} ->", basket)
    prev = code

G(3): 000 001 011 010 110 111 101 100
n =  1:    2 words, cyclic one-bit: True, all distinct: True, k xor (k>>1): True
n =  2:    4 words, cyclic one-bit: True, all distinct: True, k xor (k>>1): True
n =  3:    8 words, cyclic one-bit: True, all distinct: True, k xor (k>>1): True
n =  4:   16 words, cyclic one-bit: True, all distinct: True, k xor (k>>1): True
n =  8:  256 words, cyclic one-bit: True, all distinct: True, k xor (k>>1): True
n = 12: 4096 words, cyclic one-bit: True, all distinct: True, k xor (k>>1): True
001 add    tel -> ['tel']
011 add    dal -> ['dal', 'tel']
010 remove tel -> ['dal']
110 add    cha -> ['cha', 'dal']
111 add    tel -> ['cha', 'dal', 'tel']
101 remove dal -> ['cha', 'tel']
100 remove tel -> ['cha']

৪ · Lexicographic ক্রমে permutation — next permutation algorithm

{1, 2, 3}-এর ৬টি permutation lexicographic ক্রমে: 123, 132, 213, 231, 312, 321. প্রথমটি ছোট থেকে বড় সাজানো, শেষটি বড় থেকে ছোট। প্রশ্ন: যেকোনো একটি permutation দেওয়া থাকলে ঠিক পরেরটি কীভাবে বের করবেন, সব তালিকা না বানিয়ে? 1 4 3 2-এর পরে কী? ভাবুন: 1 দিয়ে শুরু হওয়া permutation-গুলোর মধ্যে 1 4 3 2 সবচেয়ে বড়, কারণ বাকি অংশ 4 3 2 বড় থেকে ছোট সাজানো। তাই পরেরটিকে প্রথম ঘর বদলাতেই হবে, আর সবচেয়ে ছোট বদল হলো 1-এর জায়গায় 2, তারপর বাকিগুলো ছোট থেকে বড়: 2 1 3 4. এই যুক্তিকেই algorithm বানানো যায়।

1a = 1 4 3 22ডান থেকে অবর্ধমান suffix খোঁজা3pivot = suffix-এর বাঁয়ের উপাদান4suffix-এ pivot-এর চেয়ে বড়, সবচেয়ে ডানে5অদলবদল6suffix উল্টানো

প্রমাণ:

1. Suffix a_i+1 … a_n অবর্ধমান, তাই এই উপাদানগুলোর সব বিন্যাসের মধ্যে এটিই সবচেয়ে বড়। ফলে a₁ … a_i দিয়ে শুরু কোনো permutation a-এর চেয়ে বড় নয়। — lexicographic ক্রমের সংজ্ঞা
2. অতএব a-এর চেয়ে বড় যেকোনো c, a থেকে প্রথম আলাদা হয় কোনো ঘর p ≤ i-তে, সেখানে বড় মান নিয়ে। যাদের p = i (প্রথম i − 1টি ঘর a-এর মতো), তারা p < i এমন সবার আগে আসে, কারণ ঘর p-তে তারা a-এর ছোট মানটিই রাখে। p = i দলটি ফাঁকা নয়, কারণ a_i+1 > a_i ঘর i-তে বসতে পারে। তাই পরেরটি এই দলে। — ধাপ ১
3. p = i দলের সবচেয়ে ছোট সদস্য পেতে i নম্বর ঘরে বসাতে হবে suffix-এর উপাদানগুলোর মধ্যে a_i-এর চেয়ে বড় সবচেয়ে ছোটটি, আর বাকি ঘরে বাকি উপাদান ছোট থেকে বড়। — ক্রমের সংজ্ঞা
4. Suffix অবর্ধমান বলে a_i-এর চেয়ে বড় সবচেয়ে ডানের উপাদান a_j-ই তাদের মধ্যে সবচেয়ে ছোট। অদলবদলের পর suffix-এ j-এর বাঁয়ের মানগুলো ≥ a_j > a_i, আর ডানের মানগুলো ≤ a_i (j সবচেয়ে ডানের বড় উপাদান বলে), তাই নতুন suffix-ও অবর্ধমান। — suffix-এর গঠন
5. অবর্ধমান তালিকা উল্টালে তা ছোট থেকে বড় হয়। তাই ফল b ঠিক ধাপ ৩-এর বর্ণনার permutation, অর্থাৎ a-এর ঠিক পরেরটি। ∎ — ধাপ ৩, ৪

খরচ: একটি কলের কাজ মোটামুটি suffix-এর দৈর্ঘ্য L-এর সমানুপাতিক। কয়েকটি কল দীর্ঘ (শেষের কাছে L = n), কিন্তু গড়ে খরচ ছোট। L ≥ j হয় ঠিক তখন, যখন শেষ j-টি উপাদান অবর্ধমান; সব n! permutation-এর মধ্যে এমনগুলোর ভগ্নাংশ 1/j!, কারণ শেষ j-টি ঘরে যে j-টি মানই থাকুক, তাদের j!টি বিন্যাসের ঠিক একটি অবর্ধমান। গড় L = ∑_j≥1 (L ≥ j এমনগুলোর ভগ্নাংশ), তাই গড় L = ∑_j=1ⁿ 1/j!, যা n বাড়লে e − 1 ≈ 1.718-এর দিকে যায়। অর্থাৎ পুরো তালিকা তৈরিতে প্রতি permutation-এ গড়ে ধ্রুবক কাজ (DSA কোর্সের amortized analysis-এর ভাষায়)। Scratch-এ n = 8-এর সব 40320টি permutation-এ গড় L মেপে 1.71828 পাওয়া গেছে, সূত্রের সঙ্গে হুবহু।

নিচের ব্লক algorithm-টি লিখে তার তৈরি পুরো তালিকা itertools.permutations-এর তালিকার সঙ্গে মেলায়। লক্ষ করুন, ধাপ ১ আর ২-এ >= আর <= ব্যবহার করায় একই উপাদান একাধিকবার থাকলেও algorithm চলে, আর তখন শুধু আলাদা বিন্যাসগুলো দেয়।

from itertools import permutations
from math import factorial

def next_perm(a):
    """next arrangement of a in lexicographic order, or None if a is last"""
    a = list(a)
    i = len(a) - 2
    while i >= 0 and a[i] >= a[i + 1]:   # step 1: find the pivot
        i -= 1
    if i < 0:
        return None                       # fully non-increasing: the last one
    j = len(a) - 1
    while a[j] <= a[i]:                   # step 2: rightmost element > pivot
        j -= 1
    a[i], a[j] = a[j], a[i]               # step 3: swap
    a[i + 1:] = reversed(a[i + 1:])       # step 4: suffix becomes increasing
    return a

def all_by_next(start):
    out, p = [], sorted(start)
    while p is not None:
        out.append(tuple(p))
        p = next_perm(p)
    return out

print("after 1 4 3 2 :", next_perm([1, 4, 3, 2]))
print("after 3 5 4 2 1:", next_perm([3, 5, 4, 2, 1]))
for n in range(1, 8):
    ours = all_by_next(range(1, n + 1))
    same = ours == list(permutations(range(1, n + 1)))
    print(f"n = {n}: {len(ours):5} arrangements, n! = {factorial(n):5}, same order as itertools: {same}")
words = ["".join(w) for w in all_by_next("BAZAR")]   # A repeats
print(len(words), "arrangements of BAZAR; first five:", words[:5])

after 1 4 3 2 : [2, 1, 3, 4]
after 3 5 4 2 1: [4, 1, 2, 3, 5]
n = 1:     1 arrangements, n! =     1, same order as itertools: True
n = 2:     2 arrangements, n! =     2, same order as itertools: True
n = 3:     6 arrangements, n! =     6, same order as itertools: True
n = 4:    24 arrangements, n! =    24, same order as itertools: True
n = 5:   120 arrangements, n! =   120, same order as itertools: True
n = 6:   720 arrangements, n! =   720, same order as itertools: True
n = 7:  5040 arrangements, n! =  5040, same order as itertools: True
60 arrangements of BAZAR; first five: ['AABRZ', 'AABZR', 'AARBZ', 'AARZB', 'AAZBR']

৫ · r-combination তৈরি, আর ranking ও unranking

{1, …, n}-এর একটি r-উপাদানের combination-কে সবসময় ছোট থেকে বড় লিখুন: c₁ < c₂ < … < c_r. তখন lexicographic ক্রমে n = 5, r = 2-এর ১০টি: 12, 13, 14, 15, 23, 24, 25, 34, 35, 45. খেয়াল করুন, i নম্বর ঘরের সর্বোচ্চ সম্ভাব্য মান n − r + i, কারণ তার ডানে আরও r − i-টি বড় সংখ্যার জায়গা রাখতে হয় (n = 5, r = 2-এ প্রথম ঘর বড়জোর 4, দ্বিতীয়টি বড়জোর 5).

শুদ্ধতার যুক্তি next permutation-এর মতোই। (১) i-এর ডানের সব ঘর সর্বোচ্চে, তাই c₁ … c_i দিয়ে শুরু কোনো বড় combination নেই। (২) তাই পরেরটি i নম্বর ঘর বাড়াবে, আর সবচেয়ে কম বাড়ানো হলো 1; মান c_i + 1 ব্যবহারযোগ্য, কারণ তা c_i+1-এর সমান হলে c_i+1 সর্বোচ্চে থাকায় c_i-ও সর্বোচ্চে থাকত। (৩) বাকি ঘরে সম্ভাব্য সবচেয়ে ছোট মান, অর্থাৎ পরপর সংখ্যা। যেমন n = 6-এ {1, 5, 6}: ঘর ৩ আর ২ সর্বোচ্চে (6 আর 5), ঘর ১-এ 1 < 4, তাই পরেরটি {2, 3, 4}.

Ranking আর unranking

তালিকায় একটি বস্তুর অবস্থান (০ থেকে গুনে) তার rank. বস্তু থেকে rank বের করা ranking, আর rank থেকে বস্তু unranking. কাজে লাগে অনেক জায়গায়: একটি combination-কে একটি পূর্ণসংখ্যা হিসেবে সংরক্ষণ, তালিকার মাঝখান থেকে কাজ শুরু (যেমন দুটি কম্পিউটারে অর্ধেক অর্ধেক ভাগ), আর একটি এলোমেলো পূর্ণসংখ্যা বেছে unrank করে সমান সম্ভাবনায় একটি এলোমেলো বস্তু পাওয়া।

Permutation-এর rank (Lehmer code): a₁ … a_n-এর প্রতিটি ঘরে d_i = ডানে থাকা a_i-এর চেয়ে ছোট উপাদানের সংখ্যা। তাহলে rank = ∑ d_i · (n − i)!. কারণ a₁-এর চেয়ে ছোট d₁টি মানের যেকোনোটি দিয়ে শুরু প্রতিটি permutation আগে আসে, আর প্রতিটি শুরুর জন্য (n − 1)!টি; তারপর একই যুক্তি দ্বিতীয় ঘরে। যেমন 3 1 4 2-এ d = (2, 0, 1, 0), rank = 2 · 3! + 0 + 1 · 1! + 0 = 13, অর্থাৎ ২৪টির মধ্যে ১৪ নম্বর।

Combination-এর rank: এখানে একটি অদ্ভুত সুন্দর সূত্র আছে, তবে lexicographic-এর বদলে একটু ভিন্ন ক্রমে, যার নাম colex (co-lexicographic): দুটি subset তুলনায় আগে বড় উপাদান দেখা হয়। উপাদান ০ থেকে গুনলে {0, 1, …}-এর 3-subset-গুলো colex ক্রমে {0,1,2}, {0,1,3}, {0,2,3}, {1,2,3}, {0,1,4}, …

প্রমাণ (k-এর ওপর induction):

1. Colex ক্রমে T, S-এর আগে মানে: দুটির যে বৃহত্তম উপাদানে পার্থক্য, সেটি S-এ আছে। — সংজ্ঞা
2. S-এর আগের T দুই ধরনের। (ক) max T < c_k: এরা {0, …, c_k − 1}-এর সব k-subset, সংখ্যায় C(c_k, k). (খ) max T = c_k: তখন T − {c_k}-কে colex-এ S − {c_k}-এর আগে আসতে হয়, দুটিই {0, …, c_k − 1}-এর (k − 1)-subset. (max T > c_k হলে T পরে আসে।) — ধাপ ১
3. Inductive hypothesis অনুযায়ী (খ)-এর সংখ্যা C(c₁, 1) + … + C(c_k−1, k − 1); ভিত্তি k = 1-এ {c₁}-এর আগে আছে c₁টি একক সেট = C(c₁, 1). — induction
4. যোগের নিয়মে rank(S) = ∑ C(c_i, i). Colex একটি সম্পূর্ণ ক্রম, আর C(n, k)টি subset-এর প্রতিটির rank তার আগে কয়টি আছে, তাই rank-গুলো ঠিক 0, 1, …, C(n, k) − 1, প্রতিটি একবার। ∎ — যোগের নিয়ম

Unranking লোভী (greedy) পদ্ধতিতে চলে: c_k হলো সবচেয়ে বড় c যেখানে C(c, k) ≤ N; N থেকে তা বাদ দিয়ে একই কাজ k − 1-এ। যেমন N = 100, k = 3: C(9, 3) = 84 ≤ 100 < 120 = C(10, 3), তাই c₃ = 9, বাকি 16; C(6, 2) = 15 ≤ 16 < 21, তাই c₂ = 6, বাকি 1; C(1, 1) = 1, তাই c₁ = 1. উত্তর {1, 6, 9}. পরের ব্লক দুটি দাবিই পরীক্ষা করে।

from itertools import combinations
from math import comb

def next_comb(c, n):            # next r-subset of {1..n}, lexicographic
    c, r = list(c), len(c)
    i = r - 1
    while i >= 0 and c[i] == n - r + i + 1:     # c[i] is at its maximum
        i -= 1
    if i < 0:
        return None
    c[i] += 1
    c[i + 1:] = range(c[i] + 1, c[i] + r - i)   # smallest possible tail
    return c
for n, r in [(5, 2), (6, 3), (10, 4)]:
    ours, c = [], list(range(1, r + 1))
    while c is not None:
        ours.append(tuple(c))
        c = next_comb(c, n)
    print(f"n={n}, r={r}: {len(ours)} subsets, C(n,r)={comb(n, r)},",
          "same as itertools:", ours == list(combinations(range(1, n + 1), r)))
print("after {1, 5, 6} in n = 6:", next_comb([1, 5, 6], 6))
def rank(s):                    # combinatorial number system (0-based items)
    return sum(comb(c, i + 1) for i, c in enumerate(sorted(s)))
def unrank(N, k):               # greedy: largest c with C(c, i) <= N
    out = []
    for i in range(k, 0, -1):
        c = i - 1
        while comb(c + 1, i) <= N:
            c += 1
        out.append(c)
        N -= comb(c, i)
    return sorted(out)
ranks = sorted(rank(s) for s in combinations(range(10), 3))
print("ranks of all 3-subsets of 0..9 are 0..119:", ranks == list(range(120)))
print("unrank(100, 3) =", unrank(100, 3), " rank back:", rank(unrank(100, 3)))

n=5, r=2: 10 subsets, C(n,r)=10, same as itertools: True
n=6, r=3: 20 subsets, C(n,r)=20, same as itertools: True
n=10, r=4: 210 subsets, C(n,r)=210, same as itertools: True
after {1, 5, 6} in n = 6: [2, 3, 4]
ranks of all 3-subsets of 0..9 are 0..119: True
unrank(100, 3) = [1, 6, 9]  rank back: 100

৬ · এলোমেলো permutation — Fisher–Yates আর তার সমতার প্রমাণ

সব permutation তালিকা করার বদলে কখনো দরকার শুধু একটি এলোমেলো permutation, যেখানে n!টির প্রতিটি সমান সম্ভাবনায় আসবে: ঈদের অফারে ক্রেতাদের সারি, পরীক্ষায় প্রশ্নের ক্রম, বা একটি algorithm-এর জন্য এলোমেলো ইনপুট। কম্পিউটারে এলোমেলো সংখ্যা আসে একটি pseudorandom number generator থেকে; এখানে ধরে নিই, সেটি 0 থেকে i-এর মধ্যে প্রতিটি পূর্ণসংখ্যা সমান সম্ভাবনায় আর আগের পছন্দ থেকে স্বাধীনভাবে দেয়। সমাধানটির নাম Fisher–Yates shuffle:

বাজারঘরের লাকি ড্রয়ে বাক্স থেকে একটি একটি করে টিকিট তোলার কথা ভাবুন: প্রথমে বাক্সের যেকোনো টিকিট সমান সম্ভাবনায় শেষ ঘরে যায়, তারপর বাকিদের মধ্য থেকে একটি তার আগের ঘরে, এভাবে। Algorithm-টি ঠিক এই কাজ করে, শুধু তোলা টিকিট আলাদা বাক্সে না রেখে একই তালিকার ডান অংশে রাখে।

1a = A B C D2i = 3: j ∈ {0..3}3i = 2: j ∈ {0..2}4i = 1: j ∈ {0, 1}5ফল আর সম্ভাবনা

প্রমাণ (n-এর ওপর induction):

1. ভিত্তি n = 1: কোনো ধাপ নেই, একমাত্র permutation-টি সম্ভাবনা 1 = 1/1!-এ আসে। — সরাসরি
2. n ≥ 2-এ প্রথম ধাপ (i = n − 1) শেষ ঘরে বসায় a[j], যেখানে j সমান সম্ভাবনায় 0..n − 1 থেকে। উপাদানগুলো আলাদা, তাই π-এর শেষ উপাদান শেষ ঘরে আসে ঠিক একটি j-তে: সম্ভাবনা 1/n. — uniform পছন্দ
3. এরপর বাকি ধাপগুলো (i = n − 2, …, 1) শুধু প্রথম n − 1টি ঘরে কাজ করে, আর সেগুলো হুবহু সেই n − 1টি উপাদানের ওপর Fisher–Yates. তাদের পছন্দ প্রথম পছন্দ থেকে স্বাধীন। — algorithm-এর গঠন
4. Inductive hypothesis অনুযায়ী প্রথম n − 1টি ঘর π-এর প্রথম n − 1টির মতো হওয়ার সম্ভাবনা 1/(n − 1)!. — induction
5. স্বাধীনতার জন্য গুণ: 1/n · 1/(n − 1)! = 1/n!. ∎ — গুণের নিয়ম

গণনার ভাষায় একই কথা: n · (n − 1) ⋯ 2 = n!টি সমান সম্ভাব্য পছন্দের ক্রম আছে, আর প্রমাণটি দেখায় প্রতিটি permutation ঠিক একটি ক্রম থেকে আসে, অর্থাৎ পছন্দের ক্রম থেকে permutation-এ একটি bijection. সম্ভাবনার পূর্ণ কাঠামো পর্ব ৩৮ “বিচ্ছিন্ন সম্ভাবনা — sample space, event আর Laplace-এর সংজ্ঞা”-এ আসবে; algorithm হিসেবে Fisher–Yates আর reservoir sampling-এর আলোচনা DSA কোর্সের পর্ব ৬১-এ আছে।

প্রমাণ (বিরোধ দিয়ে):

1. এখানে প্রতিটি ধাপে n-টি পছন্দ, তাই nⁿটি সমান সম্ভাব্য পছন্দের ক্রম; প্রতিটি permutation-এর সম্ভাবনা (তাকে দেওয়া ক্রমের সংখ্যা)/nⁿ. — গুণের নিয়ম
2. ধরুন বণ্টন uniform. তাহলে প্রতিটি permutation পায় nⁿ/n!টি ক্রম, যা পূর্ণসংখ্যা হতে হবে, অর্থাৎ n! ∣ nⁿ. — বিরোধের অনুমান
3. n − 1 ∣ n!, তাই n − 1 ∣ nⁿ হতো। কিন্তু gcd(n − 1, n) = 1, ফলে gcd(n − 1, nⁿ) = 1 (পর্ব ২১). n ≥ 3-এ n − 1 ≥ 2, তাই n − 1 ∤ nⁿ. বিরোধ। ∎ — gcd-এর ধর্ম

শেষ ব্লকটি দুটি shuffle-কে n = 6-এ ৭২,০০০ বার চালায় (প্রতিটি permutation গড়ে ১০০ বার আসা উচিত), আর প্রতিটির জন্য chi-square statistic হিসাব করে: ∑ (দেখা − প্রত্যাশিত)² / প্রত্যাশিত. সত্যিই uniform হলে এর গড় মান মোটামুটি ঘরের সংখ্যা − 1 = 719, আর সাধারণ ওঠানামা প্রায় ±38; অনেক বড় মান মানে পক্ষপাত। তারপর n = 3-এ ভুল সংস্করণের সব 27টি পছন্দের ক্রম একবার করে চালিয়ে নির্ভুল গণনা দেখায়। প্রতিটি generator-এ seed দেওয়া, তাই প্রতিবার একই ফল।

import random
from collections import Counter
from itertools import permutations, product

def fisher_yates(a, rng):
    a = list(a)
    for i in range(len(a) - 1, 0, -1):
        j = rng.randint(0, i)            # 0 <= j <= i
        a[i], a[j] = a[j], a[i]
    return tuple(a)

def naive(a, rng):                       # the common wrong version
    a = list(a)
    for i in range(len(a)):
        j = rng.randint(0, len(a) - 1)   # any position, every time
        a[i], a[j] = a[j], a[i]
    return tuple(a)
def chi_square(shuffle, seed, n=6, trials=72_000):
    rng = random.Random(seed)
    counts = Counter(shuffle(range(n), rng) for _ in range(trials))
    expected = trials / 720              # 6! = 720 outcomes, 100 each
    return sum((counts[p] - expected) ** 2 / expected
               for p in permutations(range(n)))

for seed in (1, 2, 3):
    print(f"seed {seed}: chi2 Fisher-Yates {chi_square(fisher_yates, seed):6.1f},"
          f"  naive {chi_square(naive, seed):6.1f}  (df = 719)")
# exact count for n = 3: every sequence of random choices, once
exact = Counter()
for js in product(range(3), repeat=3):   # 3^3 = 27 equally likely runs
    a = list("ABC")
    for i, j in enumerate(js):
        a[i], a[j] = a[j], a[i]
    exact["".join(a)] += 1
print("naive, n = 3, out of 27:", dict(sorted(exact.items())))

seed 1: chi2 Fisher-Yates  716.7,  naive 6394.6  (df = 719)
seed 2: chi2 Fisher-Yates  700.5,  naive 5770.1  (df = 719)
seed 3: chi2 Fisher-Yates  802.0,  naive 5491.3  (df = 719)
naive, n = 3, out of 27: {'ABC': 4, 'ACB': 5, 'BAC': 5, 'BCA': 5, 'CAB': 4, 'CBA': 4}

৭ · শর্তযুক্ত বস্তু — backtracking, আর সব কিছু তৈরির খরচ

এখন পর্যন্ত যে বস্তুগুলো তৈরি করেছি, তাদের ওপর কোনো শর্ত ছিল না। কিন্তু প্রায়ই দরকার শুধু শর্ত মানা বস্তুগুলো: যেমন n × n দাবার বোর্ডে n-টি রানি, কোনো দুটি একই সারি, কলাম বা কোণাকুণিতে নয় (N-queens). প্রতিটি সারিতে একটি রানি, তাই একটি সমাধান হলো “কোন সারিতে কোন কলাম” এর একটি permutation, যেখানে কোণাকুণির শর্তও মানা হয়েছে। সরল পথ: সব n! permutation তৈরি করে প্রতিটি পরীক্ষা। ভালো পথ: backtracking, অর্থাৎ সারি ধরে ধরে রানি বসানো, আর কোনো আংশিক বসানো শর্ত ভাঙলেই সেই শাখার বাকিটা না দেখে পিছিয়ে আসা।

গাণিতিকভাবে backtracking একটি গাছ ঘুরে দেখে, যার নাম state-space tree: root খালি বোর্ড, প্রতিটি সন্তান একটি নতুন সিদ্ধান্ত যোগ করে, আর গভীরতা n-এর পাতাগুলো পূর্ণ বস্তু। শর্তহীন অবস্থায় এই গাছের পাতাগুলো ঠিক সব permutation, আর গাছের depth-first ভ্রমণ এগুলো lexicographic ক্রমেই দেয়; অর্থাৎ next permutation আর backtracking একই তালিকার দুই রূপ। শর্ত এলে গাছ ছাঁটা (pruning) হয়। Scratch-এ চালানো একটি সরল N-queens backtracking-এর গণনা:

n = 1 থেকে 10 পর্যন্ত সমাধানের সংখ্যা 1, 0, 0, 2, 10, 4, 40, 92, 352, 724 (scratch-এ গোনা)। লক্ষ করুন, ক্রম নিয়মিত নয়: n = 6-এ মাত্র ৪টি, n = 5-এ ১০টি। n = 8-এ backtracking ২,০৫৭টি অবস্থা দেখে, যেখানে সব permutation পরীক্ষায় ৪০,৩২০টি আর “প্রতি সারিতে যেকোনো কলাম” পরীক্ষায় প্রায় ১.৬৮ কোটি। কোড আর pruning-এর কৌশল DSA কোর্সের পর্ব ৫৬-এ আছে; এখানে মূল কথা গাণিতিক: backtracking একই bijection-ভিত্তিক তালিকা, শুধু অচল শাখা বাদ দিয়ে।

সব তৈরি করা কখন অসম্ভব

ভালো generator প্রতি বস্তুতে গড়ে ধ্রুবক কাজ করে, কিন্তু বস্তুর সংখ্যাই যদি বিশাল হয়, কোনো কৌশল বাঁচাতে পারে না। একে বলে combinatorial explosion. ধরুন একটি কম্পিউটার সেকেন্ডে ১০ কোটি (10⁸) permutation পরীক্ষা করতে পারে (একটি আনুমানিক ধারণা মাত্র):

তাই ২০টি ঠিকানার ডেলিভারি রুটের জন্য সব ক্রম তৈরি করে সেরাটি বাছা বাস্তবে সম্ভব নয়; সেখানে লাগে DP, branch and bound বা আনুমানিক algorithm, যা DSA কোর্সে আছে (বৃদ্ধির হারের তুলনা পর্ব ৪-এ)। “সব তৈরি করুন” কৌশলের সঠিক জায়গা হলো ছোট n: সূত্র যাচাই, প্রতিটি ছোট ইনপুটে একটি প্রোগ্রাম পরীক্ষা, আর counterexample খোঁজা, যা এই কোর্সে আমরা বারবার করছি।

৮ · পরীক্ষার অঙ্ক আর গণনার একটি ভুল প্রমাণ

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় এই ধাঁচের অঙ্ক আসে। প্রতিটি উত্তর scratch-এ Python দিয়ে মেলানো।

অঙ্ক ১: 1 2 5 4 3-এর পরের permutation, আর 3 5 4 2 1-এর rank

1. 1 2 5 4 3: suffix 5 4 3, pivot 2; suffix-এ 2-এর চেয়ে বড় সবচেয়ে ডানের 3. অদলবদলে 1 3 5 4 2, suffix উল্টে 1 3 2 4 5.
2. 3 5 4 2 1-এর Lehmer code: 3-এর ডানে ছোট 2টি (2, 1), 5-এর ডানে 3টি, 4-এর ডানে 2টি, 2-এর ডানে 1টি: d = (2, 3, 2, 1, 0). rank = 2 · 24 + 3 · 6 + 2 · 2 + 1 · 1 = 71 (০ থেকে গুনে), অর্থাৎ ১২০টির মধ্যে ৭২ নম্বর। যুক্তিতেও মেলে: 3 দিয়ে শুরু ২৪টি permutation-এর এটি শেষটি, আর 1 ও 2 দিয়ে শুরু ৪৮টি আগে আছে: 48 + 23 = 71.

অঙ্ক ২: 4-বিট reflected Gray code-এর ১০ নম্বর শব্দ (০ থেকে গুনে)

1. k = 10 = 1010, k ≫ 1 = 0101. XOR: 1111.
2. যাচাই: G(4) = 0·G(3), 1·G(3)^R; ১০ নম্বর হলো দ্বিতীয় অর্ধেকের ২ নম্বর (০ থেকে)। G(3)^R = 100, 101, 111, …-এর ২ নম্বর 111, আগে 1 বসিয়ে 1111 ✓.

অঙ্ক ৩: combination

1. n = 7-এ {2, 5, 6, 7}-এর পরের 4-combination: ঘর ৪, ৩, ২ সর্বোচ্চে (7, 6, 5), ঘর ১-এ 2 < 4. 2 → 3, তারপর 4, 5, 6: {3, 4, 5, 6}.
2. Combinatorial number system-এ 50, k = 4: C(7, 4) = 35 ≤ 50 < 70, বাকি 15; C(5, 3) = 10 ≤ 15 < 20, বাকি 5; C(3, 2) = 3 ≤ 5 < 6, বাকি 2; C(2, 1) = 2. উত্তর {2, 3, 5, 7}.

প্রমাণের ভুল ধরুন: “৫টি পণ্য থেকে ৩টির দল ৬০টি”

একজন লিখলেন: “দাবি: ৫টি পণ্য থেকে ৩টির কম্বো দল 60টি। প্রমাণ: আমার generator permutations(items, 3) চালিয়ে প্রতিটি ফলাফলকে একটি দল হিসেবে নিয়েছে; সেটি 5 · 4 · 3 = 60টি ফল দিয়েছে, আর প্রতিটি ফলাফলে ৩টি আলাদা পণ্য আছে, তাই প্রতিটিই একটি বৈধ দল। অতএব দল 60টি। ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: “প্রতিটি ফলাফল একটি বৈধ দল” দেখায় শুধু যে generator-এর ফল থেকে দলে একটি ফাংশন আছে, যা onto. কিন্তু গণনার সমতার জন্য দরকার bijection, আর ফাংশনটি one-to-one নয়: (চা, ডাল, তেল), (ডাল, চা, তেল) সহ ৩! = 6টি ক্রম একই দল দেয়। এটি পুরোনো overcounting-এর ভুল, generator-এর আড়ালে। প্রতিটি দল ঠিক ৬ বার আসে বলে ভাগের নিয়মে উত্তর 60/6 = 10 = C(5, 3). Counterexample দিয়েও ধরা যায়: ৩টি পণ্য থেকে ৩টির দল স্পষ্টতই ১টি, অথচ যুক্তিটি 3! = 6 বলত। শিক্ষা: generator-এর তালিকার দৈর্ঘ্যকে সংখ্যা ধরার আগে প্রমাণ করুন যে কোনো বস্তু দুবার আসে না, অথবা len(set(...)) দিয়ে মিলিয়ে নিন।

৯ · AI-এর যুগে — তৈরি করা কোড আর গণনার দাবি যাচাই

“সব permutation তৈরি করো” বা “একটি shuffle লেখো” এমন অনুরোধে AI সহকারী দ্রুত কোড দেয়, আর কোডটি প্রায়ই দেখতে ঠিক। কিন্তু এই বিষয়ে কয়েকটি ভুল নিয়মিত দেখা যায়, আর সবগুলোই ছোট n-এ সব তালিকা করে মেলালেই ধরা পড়ে:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• ছোট n-এ তালিকার দৈর্ঘ্য গোনার সূত্রের (n!, C(n, r), 2ⁿ) সমান, আর len(set)-ও একই
• ক্রম lexicographic কি না, itertools-এর সঙ্গে হুবহু মিলিয়েছি
• পুনরাবৃত্ত উপাদান, n = 0 আর n = 1-এর মতো প্রান্তিক ইনপুটে চালিয়েছি
• Shuffle-এ j-এর পরিসর 0..i, আর n = 3-এ সব পছন্দ চালিয়ে প্রতিটি ফল সমান সংখ্যকবার এসেছে
• প্রমাণের প্রতিটি ধাপের যুক্তি আর অনুমান পড়ে দেখেছি; induction-এ ভিত্তি আছে
• উদ্ধৃত ইতিহাস, সাল বা বইয়ের নাম বিশ্বস্ত উৎসে মিলিয়েছি

Generator যাচাইয়ের সবচেয়ে শক্তিশালী হাতিয়ার আপনি নিজেই এই পর্বে বানিয়েছেন: ছোট n-এ সব বস্তু তৈরি করে গোনা, আর একটি বিশ্বস্ত তালিকার সঙ্গে মেলানো। AI যত সুন্দর ব্যাখ্যাই দিক, পাঁচ লাইনের এই পরীক্ষা চালানোর আগে কোডটি বিশ্বাস করবেন না।