009 — Permutations¶

Source¶

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/)

1. Problem in simple words¶

আলাদা আলাদা সংখ্যার একটা 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!)

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

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

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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-কেও বদলে দিত।

6. Real-life analogy¶

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

7. Visual explanation¶

প্রতি level-এ branch = বাকি unused item। [1, 2, 3]-এর decision tree (একটা শাখা পুরো খোলা):

                         go([])
            1 /            2 |            \ 3
       go([1])          go([2])          go([3])
      2 /   \ 3        1 /   \ 3        1 /   \ 2
  go([1,2]) go([1,3]) ...              ...
     | 3       | 2
 [1,2,3]   [1,3,2]      (প্রতি পূর্ণ শাখায় একটা permutation)

leaf (len(path) == n) = 6 = 3! permutation।

8. Example input and 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টা)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা 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)

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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।

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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!।

15. Python solution¶

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!")

16. Line-by-line code explanation¶

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 পরিষ্কার থাকে।

17. Output walkthrough¶

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!।

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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 লাগে।

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

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)

23. Pattern learned¶

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

24. Final summary¶

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

25. JavaScript solution (with test cases)¶

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] আবশ্যক।

26. TypeScript solution (with test cases)¶

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-এর স্বাভাবিক আকৃতি।

27. কোথায় কাজে লাগে (real-world use)¶

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।