040 — Permutation Basic¶
Factorial শিখে এলে — এবার তার ঠিক পরের ধাপ। প্রশ্নটা একটু বদলায়: পুরো দলকে নয়, n জন থেকে শুধু r জনকে সাজাতে হবে। এই "r জন বেছে সারিতে সাজানো"-ই permutation। মূল মন্ত্র এক লাইনে: order matters — কে আগে, কে পরে, সেটা গুরুত্বপূর্ণ। এই একটা প্রশ্নই permutation আর combination-কে আলাদা করে দেয়।
Source¶
- Original source: Classic exercise (permutation fundamentals)
- Platform: Classic exercise — https://discrete.openmathbooks.org/
- Topic: Math-based programming fundamentals → Level 3: Counting & Combinatorics
- Difficulty: Easy
- Pattern: nPr (permutation / partial product)
- Basic idea inherited from: 039 — Factorial (factorial-এর প্রথম r ধাপ)
1. Problem in simple words¶
n টা আলাদা জিনিস আছে। তার মধ্যে থেকে r টা বেছে একটা সারিতে সাজাতে হবে। কত ভাবে করা যায়?
এই সংখ্যাটাকে বলে permutation, লেখা হয় P(n, r) বা nPr।
এখানে সবচেয়ে জরুরি কথা: ক্রম (order) গুরুত্বপূর্ণ। মানে A-কে আগে রেখে B-কে পরে রাখা, আর B-কে আগে রেখে A-কে পরে রাখা — এই দুটো আলাদা গোনা হবে।
যেমন 3 জন (A, B, C) থেকে 2 জন বেছে সাজানো: AB, BA, AC, CA, BC, CB — মোট 6 উপায়। এটাই P(3, 2) = 6।
2. What is the math idea?¶
মূল idea আবার সেই multiplication principle, কিন্তু এবার পুরো n ধাপ নয় — শুধু প্রথম r ধাপ:
- প্রথম জায়গায় বসাতে পারো n জনের যে কাউকে → n choice
- দ্বিতীয় জায়গায় বাকি n−1 জন → n−1 choice
- ... এভাবে r-তম জায়গায় → n−r+1 choice
মোট = n × (n−1) × ... × (n−r+1) — ঠিক r টা সংখ্যার গুণ। Factorial দিয়ে লিখলে:
কারণ n!-এর শেষ (n−r) টা গুণ কেটে গেলে প্রথম r টা গুণ-ই বাকি থাকে।
3. Which basic idea does this inherit from?¶
এটা সরাসরি 039 (Factorial)-এর উপর দাঁড়িয়ে। Factorial হলো n! = সব n টা জিনিস সাজানো। Permutation হলো তার একটা টুকরো — শুধু প্রথম r ধাপ।
সম্পর্কটা পরিষ্কার:
P(n, n) = n!(সব জনকেই সাজালে পুরো factorial)P(n, r) = n × (n−1) × ... × (n−r+1)(প্রথম r ধাপ থেমে যাও)
মানে factorial বুঝলে permutation আসলে নতুন কিছু না — শুধু "সব না নিয়ে প্রথম কয়েকটা ধাপ নাও"। আর এটাই পরের 041 (nCr)-এর সিঁড়ি: nCr = nPr কে r! দিয়ে ভাগ।
4. Real-life analogy¶
ভাবো একটা দৌড় প্রতিযোগিতায় n জন দৌড়বিদ, কিন্তু পদক মাত্র r টা — সোনা, রুপা, ব্রোঞ্জ (r = 3 ধরো)।
- সোনা পেতে পারে n জনের যে কেউ → n রকম
- রুপা পেতে পারে বাকি n−1 জন → n−1 রকম
- ব্রোঞ্জ পেতে পারে বাকি n−2 জন → n−2 রকম
মোট পদক-বিতরণ = n × (n−1) × (n−2)। এখানে order গুরুত্বপূর্ণ — A সোনা ও B রুপা পাওয়া, আর B সোনা ও A রুপা পাওয়া — সম্পূর্ণ আলাদা ফল! তাই এটা permutation, combination নয়।
5. Visual explanation¶
প্রথমে দেখো 3 জন থেকে 2 জন সাজানোর সব উপায় (গাছ):
P(3, 2): প্রথম জায়গায় 3 choice, দ্বিতীয়তে 2 choice
A B C
/ \ / \ / \
B C A C A B
--- --- --- --- --- ---
AB AC BA BC CA CB
মোট: 3 × 2 = 6 টা সাজানো
এবার দেখো factorial থেকে কীভাবে কাটা পড়ে:
P(5, 2) = 5! / 3!
5! = 5 × 4 × [3 × 2 × 1]
3! = [3 × 2 × 1] <- এই অংশটা কেটে যায়
বাকি থাকে = 5 × 4 = 20
লক্ষ করো — শুধু প্রথম r = 2 টা গুণ বাকি থাকল। তাই P(n, r) মানেই "n থেকে শুরু করে নিচের দিকে r টা সংখ্যা গুণ"।
6. Example input and output¶
input (n, r) -> output
------------------------
(3, 2) -> 6 (3 × 2)
(5, 2) -> 20 (5 × 4)
(5, 3) -> 60 (5 × 4 × 3)
(5, 0) -> 1 (কিছু না সাজানোর 1 উপায়)
(5, 5) -> 120 (P(n,n) = n! = 5!)
(4, 1) -> 4 (4 জন থেকে 1 জন = 4 উপায়)
Edge case গুলো খেয়াল করো: P(n, 0) = 1 (খালি সারির 1 উপায়), আর P(n, n) = n! (সবাইকে সাজালে পুরো factorial)। আর r > n হলে permutation অর্থহীন (যত আছে তার বেশি বাছা যায় না)।
7. Brute force thinking¶
সবচেয়ে সরাসরি পথ — সংজ্ঞা মেনে দুটো factorial আলাদা হিসাব করে ভাগ:
def factorial(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
def nPr_brute(n, r):
return factorial(n) // (factorial(n - r) * 1) # n! / (n-r)!
এটা সংজ্ঞার হুবহু অনুবাদ — P(n, r) = n! / (n−r)!। ঠিক উত্তরই দেয়।
আরেকটা সত্যিকারের brute force (verify করার জন্য): Python-এর itertools.permutations দিয়ে ছোট case-এর সব সাজানো generate করে গুনে ফেলা — formula মেলানোর সবচেয়ে নিশ্চিন্ত উপায়।
8. Why brute force may be slow¶
দুটো পুরো factorial হিসাব করার মধ্যে অপচয় আছে। n! আর (n−r)!-এর বেশিরভাগ গুণ আসলে একই — শুধু উপরের r টা গুণ আলাদা:
n = 100, r = 2 হলে:
n! = 100 × 99 × 98 × ... × 1 (100 টা গুণ)
(n-r)! = 98 × 97 × ... × 1 (98 টা গুণ)
উত্তর তো মাত্র = 100 × 99 (2 টা গুণ!)
মানে উত্তরে দরকার মাত্র 2 টা গুণ, অথচ আমরা প্রায় 200 টা গুণ করে তারপর বেশিরভাগ কেটে ফেলছি। বিশাল n-এ এটা অহেতুক ধীর (আর বিশাল মাঝপথের সংখ্যা)।
9. Better thinking¶
মূল insight: factorial-এর দরকার নেই — সরাসরি r টা সংখ্যাই গুণ করো, n থেকে শুরু করে নিচের দিকে:
def nPr(n, r):
result = 1
for i in range(n, n - r, -1): # n, n-1, ..., n-r+1
result *= i
return result
এটা ঠিক n × (n−1) × ... × (n−r+1) — ঠিক r টা গুণ, একটাও বেশি না। r = 0 হলে loop চলে না, result = 1 থাকে → P(n, 0) = 1 আপনাআপনি ঠিক।
বিশাল n, ছোট r-এ এটা অনেক দ্রুত — O(n) থেকে O(r)-এ নেমে এল।
10. Thinking tweak¶
আসল "আহা" মুহূর্ত: পুরো factorial বানিয়ে তারপর কেটো না — শুধু যতটা দরকার, ততটুকুই গুণ করো।
P(n, r)-এ দরকার ঠিক r টা সংখ্যা: n, n−1, ..., n−r+1। তাই loop চালাও n থেকে শুরু করে r ধাপ নিচে — range(n, n-r, -1)। factorial বানিয়ে ভাগ করা মানে বেশি কাজ করে আবার ফেলে দেওয়া।
এই "যতটুকু লাগে ততটুকুই হিসাব করো" চিন্তাটা combinatorics-এ বারবার লাগবে — বিশেষ করে পরের nCr-এও।
11. Step-by-step dry run¶
চলো n = 5, r = 3 চালাই — অর্থাৎ range(5, 2, -1) = 5, 4, 3:
| step (i) | result (শুরুতে) | result × i | result (পরে) |
|---|---|---|---|
| শুরু | — | — | 1 |
| 5 | 1 | 1 × 5 | 5 |
| 4 | 5 | 5 × 4 | 20 |
| 3 | 20 | 20 × 3 | 60 |
Loop শেষ (i = 2 আর যায় না) → result = 60 → P(5, 3) = 60 ✓।
আর r = 0 হলে range(5, 5, -1) খালি — loop চলে না, result = 1 → P(5, 0) = 1 ✓।
12. Python solution¶
def nPr(n, r):
"""P(n, r): n জিনিস থেকে r টা বেছে সাজানোর উপায় (order matters)।"""
if r < 0 or r > n:
return 0 # অসম্ভব ক্ষেত্রে 0
result = 1
for i in range(n, n - r, -1): # n, n-1, ..., n-r+1 (ঠিক r টা গুণ)
result *= i
return result
# --- ছোট test গুলো (সব pass করা উচিত) ---
import math
from itertools import permutations
assert nPr(3, 2) == 6
assert nPr(5, 2) == 20
assert nPr(5, 3) == 60
assert nPr(5, 0) == 1 # খালি সারি
assert nPr(5, 5) == 120 # P(n,n) = n!
assert nPr(4, 1) == 4
assert nPr(3, 5) == 0 # r > n -> অসম্ভব
# math.perm দিয়ে cross-check
for n in range(0, 9):
for r in range(0, n + 1):
assert nPr(n, r) == math.perm(n, r)
# brute force: itertools দিয়ে সব সাজানো গুনে formula মেলানো
def nPr_count(items, r):
return sum(1 for _ in permutations(items, r))
assert nPr(4, 2) == nPr_count([1, 2, 3, 4], 2) # 12
assert nPr(5, 3) == nPr_count([1, 2, 3, 4, 5], 3) # 60
print(nPr(3, 2)) # 6
print(nPr(5, 3)) # 60
print(nPr(5, 5)) # 120
print("সব test pass!")
13. Line-by-line explanation¶
পাহারা — যত আছে তার বেশি বা negative সংখ্যা বাছা যায় না, সেক্ষেত্রে উত্তর 0।
গুণফল জমানোর পাত্র, শুরুর মান 1। r = 0-এ এই 1-ই ঠিক উত্তর।
n থেকে শুরু করে n−r+1 পর্যন্ত নিচের দিকে — ঠিক r টা সংখ্যা গুণ। range(n, n-r, -1) মানে n, n−1, ... থামে n−r-এর ঠিক আগে।
verify করার brute force — itertools.permutations ছোট list-এর সব r-দৈর্ঘ্যের সাজানো বের করে, আমরা শুধু গুনি। এটা formula-র সাথে মিলিয়ে আত্মবিশ্বাস দেয়।
বাকি assert লাইনগুলো math.perm আর brute count-এর সাথে মিলিয়ে চেক করছে। সব মিললে শেষে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
তিনটা print(nPr(...)) থেকে: (3,2) → 6, (5,3) → 60, (5,5) → 120। তার আগের সব assert (math.perm ও itertools brute force-এর সাথে cross-check) চুপচাপ pass করেছে। শেষে সব test pass!।
15. Time complexity¶
O(r) — loop ঠিক r বার চলে, প্রতিবার একটা গুণ। factorial বানিয়ে ভাগ করার O(n)-এর চেয়ে ভালো, বিশেষ করে ছোট r-এ।
(সূক্ষ্ম কথা: উত্তরটা বিশাল হলে প্রতিটা গুণ আর constant থাকে না, কিন্তু interview-র মাপে O(r) ধরাই যথেষ্ট।)
16. Space complexity¶
O(1) — শুধু একটা result variable, কোনো বাড়তি list বা array নেই (উত্তর সংখ্যাটার নিজের জায়গা বাদে)।
17. Common mistakes¶
- Permutation আর combination গুলিয়ে ফেলা — "order matters?" না ভেবে formula বসানো। পদ/সারি আলাদা হলে P, শুধু দল হলে C।
- পুরো factorial বানিয়ে ভাগ —
factorial(n)//factorial(n-r)ঠিক উত্তর দেয় কিন্তু বড় n-এ অপচয়; সরাসরি r টা গুণ করো। P(n, 0)ভুল ভাবা — খালি সারির ঠিক একটা উপায়, তাইP(n, 0) = 1, 0 নয়।r > nভুলে যাওয়া — যত আছে তার বেশি বাছা অসম্ভব, উত্তর 0; check না করলে loop ভুল করতে পারে।result0 দিয়ে শুরু — গুণফল সবসময় 1 দিয়ে শুরু।
18. Harder problems that inherit this idea¶
- 041 — Combination Basic (এই repo) — nPr কে r! দিয়ে ভাগ করে nCr; এই note-ই তার ভিত্তি।
- LeetCode — Permutation Sequence (https://leetcode.com/problems/permutation-sequence/) — k-তম permutation সরাসরি বের করতে factorial/nPr-এর হিসাব।
- LeetCode — Permutations (https://leetcode.com/problems/permutations/) — সব permutation generate করা (backtracking), যার মোট সংখ্যা ঠিক nPr।
19. Pattern learned¶
Partial product (order matters) — P(n, r) = n × (n−1) × ... × (n−r+1), ঠিক r টা সংখ্যার গুণ, n থেকে নিচে। মূল signal: "সাজাও / সারিতে রাখো / পদ আলাদা" দেখলেই permutation — order গুরুত্বপূর্ণ।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "P(n,r) = n!/(n−r)! = n থেকে নিচে r টা সংখ্যার গুণ; 'order matters?' হ্যাঁ হলে permutation। factorial বানিয়ো না — শুধু r টা গুণ করো।"
পরের ধাপ → 041 — Combination Basic (এই nPr-কে r! দিয়ে ভাগ করলেই nCr — "শুধু দল, ক্রম নয়")।
ফিরে দেখা: আগের ধাপ → 039 — Factorial · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নয় — বরং "common interview pattern" / "Google-style pattern"।