009 — Permutations¶

Problem link ও উৎস

Original source: Classic backtracking exercise (all orderings)
Platform: LeetCode — https://leetcode.com/problems/permutations/
Topic: recursion / backtracking (choose each remaining)
Difficulty: Medium
Pattern: choose each remaining — প্রতি slot-এ এখনো unused প্রতিটা item বসিয়ে দেখো (n!)
Basic idea inherited from: Subsets + seen-set (../../05-hashing/)

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

আলাদা আলাদা সংখ্যার একটা list nums দেওয়া আছে। তোমার কাজ: এর সব permutation বের করা — মানে যত রকমভাবে সবগুলো element সাজানো যায়, প্রতিটা ক্রম। Subsets-এ কোন কোন item নেব সেটা ঠিক করতাম; এখানে সব item-ই নিতে হবে, শুধু কোন order-এ সেটাই প্রশ্ন। nটা element-এর জন্য মোট n!টা permutation।

উদাহরণ

nums = [1, 2, 3]
permutations = [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]   (মোট 6 = 3!)

Input ও output¶

উদাহরণ

Input : [1, 2, 3] -> Output: [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]
Input : [0, 1]    -> Output: [0,1], [1,0]

Edge case 1 (একটা): [1]  -> Output: [[1]]      (একটাই ক্রম)
Edge case 2 (খালি): []   -> Output: [[]]       (খালি permutation, মোট 1টা)

চেনা উদাহরণে বোঝা¶

তিনজন মানুষকে তিনটা চেয়ারে বসানোর কথা ভাবো। প্রথম চেয়ারে যেকোনো একজন (3 রকম); সে বসে গেলে দ্বিতীয় চেয়ারে বাকি দুজনের একজন (2 রকম); শেষ চেয়ারে যে রইলো সে (1 রকম)। যাকে একবার বসিয়েছ তাকে আর বসানো যাবে না — ঠিক used flag। সব রকম বসার বিন্যাসই হলো সব permutation।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

ভিত্তি হলো Subsets-এর branching, কিন্তু branch factor বদলে গেছে। Subsets-এ প্রতিটা item-এ ঠিক 2টা branch (নাও/বাদ দাও) ছিল। এখানে প্রতিটা slot-এ branch-এর সংখ্যা = এখনো ব্যবহার-না-হওয়া item-এর সংখ্যা (প্রথমে n, তারপর n-1, ...)। তাই একটা used-tracker লাগে — সেই ../../05-hashing/-এর seen-set pattern, যা O(1)-তে বলে কোনটা ইতিমধ্যে বসানো হয়ে গেছে।

ভেতরের যুক্তি¶

লুকানো math হলো factorial (n!): প্রথম slot-এ n রকম পছন্দ, দ্বিতীয় slot-এ বাকি n-1 রকম, এরপর n-2... তাই মোট n × (n-1) × ... × 1 = n! ক্রম। এটা rule of product-এরই রূপ, কিন্তু প্রতিটা ধাপে option একটা করে কমে কারণ ব্যবহৃত item আর নেওয়া যায় না। তাই subsets-এর 2^n-এর জায়গায় এখানে n!।

কী দিয়ে তথ্য রাখব¶

একটা list path (বর্তমান permutation গড়তে), একটা list out (সব permutation জমাতে), একটা boolean array used (কোন index বসানো হয়ে গেছে track করতে — seen-set), আর recursion-এর জন্য call stack। record করার সময় path[:] snapshot রাখি।

এটি কেন উপযুক্ত¶

used array দিয়ে "এই item কি ইতিমধ্যে বসানো?" প্রশ্নের উত্তর O(1)-তে মেলে — এটাই seen-set-এর কাজ; set না নিয়ে boolean array নিলাম কারণ index দিয়ে দেখি, তাই আরও সস্তা। path mutable বলে append/pop O(1), পুরো decision-tree জুড়ে একটাই working permutation reuse করা যায়। আর snapshot না নিলে পরের append/pop আগের record-কেও বদলে দিত।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: প্রতিটা slot-এ n রকম index ধরে নাও (n^n রকম সমন্বয়); যেগুলোতে প্রতিটা index ঠিক একবার করে আছে শুধু সেগুলো রাখো।

উদাহরণ

for every tuple of length n over indices 0..n-1:
    if tuple uses each index exactly once:
        out.append(corresponding values)

কোথায় বেশি কাজ হচ্ছে¶

এই version n^n রকম সমন্বয় তৈরি করে, কিন্তু এদের মধ্যে মাত্র n!টা বৈধ — বাকি সব repeated index-এর জন্য বাতিল। n = 5-এ n^n = 3125 বনাম n! = 120 — অর্ধেকেরও বেশি কাজ নষ্ট। used-tracker দিয়ে আমরা শুরুতেই repeated index-এর branch-এ ঢুকিই না, তাই সরাসরি n!টা বৈধ permutation-ই গড়ি, বৃথা কাজ শূন্য।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: permutation গড়া = প্রতিটা slot-এ "এখনো বাকি item-গুলোর একটা" বসানো। "সব ক্রম কী কী?" না ভেবে ভাবো "এই একটা slot-এ আমার option কী?" — locally option = unused item-গুলো, কিন্তু সব slot মিলে globally সব n! ক্রম বেরিয়ে আসে।

আরও কম কাজে সমাধান¶

path ধরে হাঁটো। base case: len(path) == len(nums) হলে snapshot record করো। নাহলে প্রতিটা index i-র উপর loop: used[i] হলে skip; নাহলে used[i]=True + path.append (choose), go(path) (explore), তারপর path.pop() + used[i]=False (un-choose)। প্রতিটা পূর্ণ শাখা একটা permutation। choose → explore → un-choose-এর নিখুঁত প্রয়োগ, সাথে একটা used-flag।

ভাবনার পরিবর্তন¶

মোচড়: দুটো dimension আলাদা করো — recursion ঠিক করে তুমি কোন SLOT ভরছ, আর loop ঠিক করে সেই slot-এ কী যাচ্ছে। এই দুটো গুলিয়ে ফেললেই permutation কঠিন লাগে; আলাদা ভাবলে এটা subsets-এর মতোই সহজ, শুধু "বাদ দাও" branch-এর জায়গায় "বাকি সবগুলো" branch।

ছবিতে বোঝা¶

[1,2,3]-এর পুরো decision tree: ছয়টি leaf-ই দেখানো। প্রতিটি child থেকে ফেরার পর সেই choice pop করে পরের child নেওয়া হয়।

graph TD
  p0["[]"]
  p1["[1]"]
  p2["[1, 2]"]
  p3["[1, 2, 3] · record"]
  p2 -->|"choose 3"| p3
  p1 -->|"choose 2"| p2
  p4["[1, 3]"]
  p5["[1, 3, 2] · record"]
  p4 -->|"choose 2"| p5
  p1 -->|"choose 3"| p4
  p0 -->|"choose 1"| p1
  p6["[2]"]
  p7["[2, 1]"]
  p8["[2, 1, 3] · record"]
  p7 -->|"choose 3"| p8
  p6 -->|"choose 1"| p7
  p9["[2, 3]"]
  p10["[2, 3, 1] · record"]
  p9 -->|"choose 1"| p10
  p6 -->|"choose 3"| p9
  p0 -->|"choose 2"| p6
  p11["[3]"]
  p12["[3, 1]"]
  p13["[3, 1, 2] · record"]
  p12 -->|"choose 2"| p13
  p11 -->|"choose 1"| p12
  p14["[3, 2]"]
  p15["[3, 2, 1] · record"]
  p14 -->|"choose 1"| p15
  p11 -->|"choose 2"| p14
  p0 -->|"choose 3"| p11

ছোট input-এ ধাপে ধাপে¶

permute([1, 2]), go(path) + used:

go([]): i=0 → used=[T,F], path=[1], go([1])।
go([1]): i=0 used, skip; i=1 → used=[T,T], path=[1,2], go([1,2]): len==2 → record [1,2]; pop → path=[1], used=[T,F]।
ফিরে go([])-তে pop 1 → path=[], used=[F,F]; i=1 → path=[2], used=[F,T]।
go([2]): i=0 → path=[2,1], record [2,1]; pop সব।
out = [[1,2],[2,1]] — 2টা = 2!।

কোড ও ব্যাখ্যা¶

Python¶

Python

def permute(nums):
    out = []
    used = [False] * len(nums)
    def go(path):
        if len(path) == len(nums):   # base case: সব slot ভরা
            out.append(path[:])      # snapshot! live path পরে বদলাবে
            return
        for i in range(len(nums)):
            if used[i]:              # এই item আগেই বসানো -> skip
                continue
            used[i] = True           # CHOOSE
            path.append(nums[i])
            go(path)                 # EXPLORE
            path.pop()               # UN-CHOOSE
            used[i] = False
    go([])
    return out

# ---- order-independent তুলনার helper (permutation-এ ভেতরের order জরুরি) ----
def norm(list_of_lists):
    return sorted(list_of_lists)     # শুধু বাইরের list sort, ভেতরের ক্রম অটুট

# ---- tests ----
assert norm(permute([1, 2, 3])) == norm(
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]])
assert len(permute([1, 2, 3])) == 6            # 3!
assert norm(permute([0, 1])) == norm([[0, 1], [1, 0]])
assert permute([1]) == [[1]]                    # একটা element
assert permute([]) == [[]]                      # খালি -> খালি permutation
assert len(permute([1, 2, 3, 4])) == 24         # 4!
print("সব test pass!")

কোডের প্রতিটি অংশ¶

used = [False] * len(nums) — কোন index বসানো হয়েছে track করার seen-set।
if len(path) == len(nums): — base case: সব slot ভরে গেছে, একটা পূর্ণ permutation।
out.append(path[:]) — path[:] snapshot; live path পরে বদলাবে।
if used[i]: continue — ইতিমধ্যে বসানো item আবার নয়।
used[i] = True; path.append(nums[i]) — CHOOSE: এই item এই slot-এ বসাও।
go(path) — EXPLORE: পরের slot ভরো।
path.pop(); used[i] = False — UN-CHOOSE: undo, যাতে পরের branch পরিষ্কার থাকে।

Output মিলিয়ে দেখা¶

permute([1,2,3]): tree-র 6টা পূর্ণ শাখায় 6টা permutation record হয়। order আলাদা আসতে পারে, তাই norm দিয়ে বাইরের list sort করে তুলনা করি — কিন্তু ভেতরের ক্রম নষ্ট করি না (permutation-এ [1,2,3] আর [3,2,1] আলাদা), তাই sorted-of-sorted নয়, শুধু outer sort। length 6 (=3!), 4-element-এ 24, একটা element-এ [[1]], খালি-তে [[]]। সব মিলে print: সব test pass!।

JavaScript ও test cases¶

JavaScript

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function permute(nums) {
  const out = [];
  const used = new Array(nums.length).fill(false);
  const go = (path) => {
    if (path.length === nums.length) {   // base case: সব slot ভরা
      out.push([...path]);               // snapshot!
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;             // এই item আগেই বসানো -> skip
      used[i] = true;                    // CHOOSE
      path.push(nums[i]);
      go(path);                          // EXPLORE
      path.pop();                        // UN-CHOOSE
      used[i] = false;
    }
  };
  go([]);
  return out;
}

// ---- order-independent তুলনা (ভেতরের ক্রম অটুট, শুধু বাইরের list sort) ----
const norm = (lol) => JSON.stringify([...lol].sort((a, b) => JSON.stringify(a).localeCompare(JSON.stringify(b))));

// ---- test cases ----
assert(norm(permute([1, 2, 3])) === norm([[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]), "main");
assert(permute([1, 2, 3]).length === 6, "3!");
assert(norm(permute([0, 1])) === norm([[0, 1], [1, 0]]), "two");
assert(JSON.stringify(permute([1])) === JSON.stringify([[1]]), "single");
assert(JSON.stringify(permute([])) === JSON.stringify([[]]), "খালি");
assert(permute([1, 2, 3, 4]).length === 24, "4!");
console.log("সব JS test pass!");

JS টীকা: এখানে দুটো dimension আলাদা — recursion ঠিক করে কোন slot ভরছি, আর for loop ঠিক করে সেই slot-এ কী যাচ্ছে। used boolean array হলো seen-set (Python-এর সমতুল্য), যা O(1)-তে বলে কোন index বসানো হয়ে গেছে। permutation-এ ভেতরের ক্রম জরুরি ([1,2,3] ≠ [3,2,1]), তাই norm-এ শুধু বাইরের list sort করি, ভেতরের element sort করি না। snapshot [...path] আবশ্যক।

TypeScript ও test cases¶

TypeScript

function permute(nums: number[]): number[][] {
  const out: number[][] = [];
  const used: boolean[] = new Array(nums.length).fill(false);
  const go = (path: number[]): void => {
    if (path.length === nums.length) {
      out.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;                    // CHOOSE
      path.push(nums[i]);
      go(path);                          // EXPLORE
      path.pop();                        // UN-CHOOSE
      used[i] = false;
    }
  };
  go([]);
  return out;
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
const norm = (lol: number[][]): string =>
  JSON.stringify([...lol].sort((a, b) => JSON.stringify(a).localeCompare(JSON.stringify(b))));

expect(norm(permute([1, 2, 3])), norm([[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]), "main");
expect(permute([1, 2, 3]).length, 6, "3!");
expect(JSON.stringify(permute([])), JSON.stringify([[]]), "empty");
expect(permute([1, 2, 3, 4]).length, 24, "4!");
console.log("সব TS test pass!");

TS টীকা: used: boolean[] টাইপ স্পষ্ট করে এটা একটা visited-flag array — number[]-এর সাথে গুলিয়ে ফেলার ভুল কম্পাইলার ধরবে। return number[][] বলে এটা ক্রম-array-র collection। go(path: number[]): void signature মনে করিয়ে দেয় recursion শুধু side-effect-এ (out-এ push) কাজ করে, কিছু return করে না — backtracking-এর স্বাভাবিক আকৃতি।

খরচ ও সাধারণ ভুল¶

সময়¶

O(n · n!) — n!টা permutation, প্রতিটার snapshot নিতে n পর্যন্ত copy। (গঠনের কাজও মোটামুটি এই bound-এ।)

অতিরিক্ত জায়গা¶

Output বাদ দিলে O(n) — path, used, আর call stack n পর্যন্ত। Output ধরলে O(n · n!)।

যে ভুলগুলো এড়াতে হবে¶

used flag না রাখা — একই item বারবার বসে যায়, permutation-এর বদলে n^n আবর্জনা।
out.append(path) লেখা (snapshot ছাড়া) — সব entry একই live list-এর reference হয়ে শেষে এক রকম হয়ে যায়; path[:] নাও।
path.pop()-এর পর used[i]=False ভুলে যাওয়া — পরের branch-এ item আটকে থাকে।
সব input distinct ধরে নেওয়া — duplicate থাকলে এই version repeated permutation দেবে; তখন Permutations II-র sorted-skip লাগে।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: Subsets (এই tracker-এর #7)-এর branching + ../../05-hashing/-এর seen-set। ../patterns.md-এর Pattern 4 (Permutations — choose each remaining) দেখো; সেখানে "recursion ঠিক করে কোন slot, loop ঠিক করে কী যাচ্ছে" frame-টা পুরো খোলা। এটা tracker-এর চারটা canonical interview shape-এর একটা — এখানে বেশি সময় দাও।

পরের অনুশীলন¶

Permutations II (duplicate সহ) — https://leetcode.com/problems/permutations-ii/ (এই tracker-এর #14)
Letter Combinations of a Phone Number — https://leetcode.com/problems/letter-combinations-of-a-phone-number/ (#8)
N-Queens (column-গুলোই একটা permutation) — https://leetcode.com/problems/n-queens/ (#19)

কৌশলটি মনে রাখুন¶

Choose-each-remaining: প্রতি slot-এ unused প্রতিটা item-এর উপর loop চালিয়ে choose → explore → un-choose, সাথে একটা used-tracker; এভাবে n! ক্রম enumerate করা — সব arrangement/ordering problem-এর মূল কঙ্কাল, আর constraint backtracking-এরও ভিত্তি।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "Permutations = প্রতি slot-এ unused item-গুলোর উপর loop, used-flag দিয়ে track, base case-এ path-এর snapshot।" যখনই 'সব ordering/arrangement' বা 'n!' শুনবে — এই choose-each-remaining backtracking skeleton মনে করবে; recursion = কোন slot, loop = কী বসছে — এই দুটো আলাদা রাখাই চাবি।

কোথায় কাজে লাগে¶

Scheduling/ordering: task, delivery-stop, বা job-এর সব সম্ভাব্য ক্রম তৈরি করে optimal sequence খোঁজা (TSP baseline)।
Test input generation: parameter-এর সব ordering দিয়ে order-dependent bug ধরা।
Anagram/word generation: অক্ষরের সব বিন্যাস তৈরি করতে।
Cryptography/brute-force: ছোট key-space-এর সব permutation যাচাই করা।
Constraint solving-এর ভিত্তি: N-Queens-এর column-placement আসলে একটা permutation — এই skeleton-ই ভিত্তি।

এক কথায়, "সব arrangement/ordering enumerate করো (n!)" শুনলেই — প্রতি slot-এ unused item-গুলোর উপর loop চালিয়ে used-flag সহ choose/explore/un-choose; এটাই সব ordering ও constraint-backtracking-এর মূল কঙ্কাল।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।