Problem link ও উৎস
- **Original source:** Classic exercise (permutation fundamentals)
- **Platform:** Classic exercise —
- **Topic:** Math-based programming fundamentals → Level 3: Counting & Combinatorics
- **Difficulty:** Easy
- **Pattern:** nPr (permutation / partial product)
- **Basic idea inherited from:** 039 — Factorial (factorial-এর প্রথম r ধাপ)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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`।
### Input ও output {#6-example-input-and-output}
```text
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 অর্থহীন (যত আছে তার বেশি বাছা যায় না)।
### চেনা উদাহরণে বোঝা {#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 নয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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! দিয়ে ভাগ।
### ভেতরের অঙ্ক {#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 দিয়ে লিখলে:
```text
P(n, r) = n! / (n − r)!
```
কারণ `n!`-এর শেষ `(n−r)` টা গুণ কেটে গেলে প্রথম r টা গুণ-ই বাকি থাকে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরাসরি পথ — সংজ্ঞা মেনে দুটো factorial আলাদা হিসাব করে ভাগ:
```python
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 টা গুণ আলাদা:
```text
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 থেকে শুরু করে নিচের দিকে:
```python
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-এও।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দেখো 3 জন থেকে 2 জন সাজানোর সব উপায় (গাছ):
```text
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 থেকে কীভাবে কাটা পড়ে:
```text
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 টা সংখ্যা গুণ"।
### ছোট input-এ ধাপে ধাপে {#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` ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
def nPr(n, r):
if r < 0 or r > n:
return 0
```
পাহারা — যত আছে তার বেশি বা negative সংখ্যা বাছা যায় না, সেক্ষেত্রে উত্তর 0।
```text
result = 1
```
গুণফল জমানোর পাত্র, শুরুর মান 1। `r = 0`-এ এই 1-ই ঠিক উত্তর।
```text
for i in range(n, n - r, -1):
result *= i
```
`n` থেকে শুরু করে `n−r+1` পর্যন্ত নিচের দিকে — ঠিক r টা সংখ্যা গুণ। `range(n, n-r, -1)` মানে n, n−1, ... থামে n−r-এর ঠিক আগে।
```text
def nPr_count(items, r):
return sum(1 for _ in permutations(items, r))
```
verify করার brute force — `itertools.permutations` ছোট list-এর সব r-দৈর্ঘ্যের সাজানো বের করে, আমরা শুধু গুনি। এটা formula-র সাথে মিলিয়ে আত্মবিশ্বাস দেয়।
বাকি `assert` লাইনগুলো `math.perm` আর brute count-এর সাথে মিলিয়ে চেক করছে। সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
6
60
120
সব test pass!
```
তিনটা `print(nPr(...))` থেকে: (3,2) → 6, (5,3) → 60, (5,5) → 120। তার আগের সব `assert` (`math.perm` ও itertools brute force-এর সাথে cross-check) চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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}
1. **Permutation আর combination গুলিয়ে ফেলা** — "order matters?" না ভেবে formula বসানো। পদ/সারি আলাদা হলে P, শুধু দল হলে C।
2. **পুরো factorial বানিয়ে ভাগ** — `factorial(n)//factorial(n-r)` ঠিক উত্তর দেয় কিন্তু বড় n-এ অপচয়; সরাসরি r টা গুণ করো।
3. **`P(n, 0)` ভুল ভাবা** — খালি সারির ঠিক একটা উপায়, তাই `P(n, 0) = 1`, 0 নয়।
4. **`r > n` ভুলে যাওয়া** — যত আছে তার বেশি বাছা অসম্ভব, উত্তর 0; check না করলে loop ভুল করতে পারে।
5. **`result` 0 দিয়ে শুরু** — গুণফল সবসময় 1 দিয়ে শুরু।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **041 — Combination Basic** (এই repo) — nPr কে r! দিয়ে ভাগ করে nCr; এই note-ই তার ভিত্তি।
- **LeetCode — Permutation Sequence** (