014 — Permutations II¶

Problem link ও উৎস

Original source: Classic backtracking exercise (unique orderings with duplicates)
Platform: LeetCode — https://leetcode.com/problems/permutations-ii/
Topic: recursion / backtracking (choose remaining + duplicate skip)
Difficulty: Medium
Pattern: choose remaining + duplicate skip — sort, তারপর nums[i]==nums[i-1] and not used[i-1] হলে skip
Basic idea inherited from: Permutations + sorted skip

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

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

একটা সংখ্যার list nums দেওয়া আছে যেখানে duplicate থাকতে পারে। তোমার কাজ: এর সব distinct permutation বের করা — মানে সব ক্রম, কিন্তু একই ক্রম দুবার নয়। সাধারণ Permutations-এ সব element আলাদা ছিল, তাই n!টা ভিন্ন ক্রম; এখানে [1, 1, 2]-এর মতো input-এ সরল permutation দুটো সমান 1-কে আলাদা ভেবে নকল ক্রম দেবে। সেই নকলগুলোই বাদ দিতে হবে।

উদাহরণ

nums = [1, 1, 2]
permutations = [1,1,2], [1,2,1], [2,1,1]   (3টা distinct, 3!=6 নয়)

Input ও output¶

উদাহরণ

Input : [1, 1, 2] -> Output: [1,1,2], [1,2,1], [2,1,1]   (3 distinct)
Input : [1, 2, 3] -> Output: 6টা (সব আলাদা -> 3!)

Edge case 1 (সব সমান): [2, 2, 2] -> Output: [[2,2,2]]    (1টা)
Edge case 2 (জোড়া):    [1, 1]    -> Output: [[1,1]]      (1টা)

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

দুটো একদম একরকম লাল বল আর একটা নীল বল সারিতে সাজানোর কথা ভাবো। দুই লাল বল দেখতে অভিন্ন, তাই তাদের নিজেদের মধ্যে অদলবদল করলে "নতুন" সাজ হয় না — চোখে একই। তাই গুনতে গেলে দুই লালকে সবসময় একই (বাঁ-থেকে-ডান) ক্রমে বসাও; তাহলে প্রতিটা দৃশ্যমান ভিন্ন সাজ একবারই গোনা হয়।

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

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

ভিত্তি হলো Permutations + sorted skip। কঙ্কাল হুবহু Permutations — প্রতি slot-এ unused প্রতিটা item বসাও, used-tracker রাখো। নতুন: আগে list sort করো (সমান মান পাশাপাশি), তারপর একই slot-এ সমান একটা মান দ্বিতীয়বার বসানোর চেষ্টা করলে — যখন আগের সমান copy এই শাখায় ব্যবহৃত হয়নি — সেটা skip করো। sort-and-skip-এর সেই পরিচিত trick, এবার ordering-এর জগতে।

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

লুকানো math হলো duplicate-সহ permutation-সংখ্যা = n! / (m₁!·m₂!·...), যেখানে mᵢ হলো প্রতিটা ভিন্ন মানের পুনরাবৃত্তি। সরল permutation সমান copy-গুলোকে আলাদা ধরে ঠিক ওই গুণনীয়কগুণ বেশি ক্রম দেয়। skip-নিয়মটা প্রতিটা distinct ক্রমকে শুধু একটাই canonical পথে গড়তে দেয় — সমান copy-গুলো সবসময় বাঁ-থেকে-ডান ক্রমে ব্যবহৃত হয়, উল্টোভাবে নয়।

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

একটা list path (বর্তমান permutation), একটা list out (ফলাফল), একটা boolean array used (কোন index বসানো), আর call stack। nums.sort() অপরিহার্য — সমান মান পাশাপাশি আনতে, যাতে প্রতিবেশী-ভিত্তিক skip কাজ করে। record-এ path[:] snapshot।

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

used array O(1)-তে বলে কোন index ব্যবহৃত — Permutations-এর মতোই seen-set। sort করা list-এ skip-শর্ত শুধু পাশের সমান element (nums[i-1]) আর তার used[i-1] দেখেই কাজ সারে — আলাদা কোনো জটিল structure লাগে না। path mutable বলে choose/un-choose O(1)। দুটো ছোট জিনিস (used + sorted neighbor) মিলে duplicate ছাড়াই সব ক্রম দেয়।

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

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

প্রথম সরল চিন্তা: সাধারণ Permutations চালিয়ে n!টা ক্রম গড়ো (সমান copy আলাদা ধরে), তারপর প্রতিটাকে tuple বানিয়ে একটা set-এ ফেলে নকল ঝেড়ে ফেলো।

উদাহরণ

all = permute(nums)                 # n!, নকল সহ
unique = set(tuple(p) for p in all)
out = [list(t) for t in unique]

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

এই version সবসময় পুরো n!টা ক্রম গড়ে — [2,2,2]-এ 6টা গড়ে অথচ distinct মাত্র 1টা — তারপর hashing দিয়ে নকল ঝাড়ে। অপচয় দুই দিকে: একই ক্রম বারবার তৈরি, আর প্রতিটা tuple hash করার O(n) খরচ। sorted-skip version নকল শাখায় ঢোকেই না, তাই সরাসরি distinct ক্রমগুলোই গড়ে; [2,2,2]-এ মাত্র 1টা পথ হাঁটে।

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

মূল observation: সমান copy-দের মধ্যে কে আগে বসবে তা গুরুত্বহীন — তাই একটা নিয়ম চাপাই: সমান copy সবসময় বাঁ-থেকে-ডান ক্রমে বসবে। nums[i] == nums[i-1] and not used[i-1] ঠিক সেই মুহূর্ত ধরে যখন তুমি একটা সমান copy বসাতে যাচ্ছ অথচ তার ঠিক-আগের সমান copy এখনো বসেনি — মানে তুমি ক্রম উল্টে ফেলছ; তাই skip।

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

nums.sort() করো। go(path): len(path) == len(nums) হলে record। নাহলে প্রতিটা i: used[i] হলে skip; i > 0 and nums[i]==nums[i-1] and not used[i-1] হলে skip (duplicate); নাহলে used[i]=True + append (choose), go(path) (explore), pop + used[i]=False (un-choose)। মূল Permutations-এ শুধু একটা skip-line যোগ হলো।

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

মোচড়: "নকল কীভাবে ঠেকাব?" — set দিয়ে পরে ঝাড়ার কথা ভেবো না। বরং একটা canonical নিয়ম চাপাও: সমান মানগুলো সবসময় তাদের original বাঁ-থেকে-ডান ক্রমে ব্যবহৃত হবে। not used[i-1] এই ক্রম-নিয়ম জোর করে — আগের সমানটা না বসিয়ে পরেরটা বসানো মানে ক্রম-ভাঙা, তাই বারণ।

ছবিতে বোঝা¶

sort করা [1, 1, 2]; প্রথম slot-এ দ্বিতীয় 1 skip (আগের সমান copy unused):

উদাহরণ

                      go([])
        1 /          1 (skip: nums[1]==nums[0], used[0]=False)      2 |
   go([1])                                                       go([2])
   1/        2\                                                   1/ (then 1)
go([1,1])  go([1,2])                                          go([2,1])->[2,1,1]
  2|          1| (used[0] True এখন -> 1 বৈধ)
[1,1,2]    [1,2,1]

leaf (len==3) = 3 distinct permutation। প্রথম slot-এর দ্বিতীয় 1 skip বলে নকল নেই।

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

permute_unique([1, 1, 2]) (sort করা একই), go(path) + used:

go([]): i=0 (1): used=[T,F,F], path=[1], go([1])।
go([1]): i=1 (1): আগের সমান copy used[0]=T → বৈধ; path=[1,1] → go([1,1]): i=2 (2): record [1,1,2]; unwind।
go([1]): i=2 (2): path=[1,2] → go([1,2]): i=1 (1, used[0]=T): record [1,2,1]; unwind সব।
go([]): i=1 (1): i>0, nums[1]==nums[0], used[0]=F → skip (নকল রোধ)।
go([]): i=2 (2): path=[2] → ভেতরে [2,1,1] record।
out = [[1,1,2],[1,2,1],[2,1,1]] — 3টা distinct।

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

Python¶

Python

def permute_unique(nums):
    nums.sort()                        # সমান মান পাশাপাশি
    out = []
    used = [False] * len(nums)
    def go(path):
        if len(path) == len(nums):     # base case: সব slot ভরা
            out.append(path[:])        # snapshot!
            return
        for i in range(len(nums)):
            if used[i]:
                continue               # ইতিমধ্যে বসানো
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue               # আগের সমান copy এখনো বসেনি -> নকল রোধ
            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_unique([1, 1, 2])) == norm([[1, 1, 2], [1, 2, 1], [2, 1, 1]])
assert len(permute_unique([1, 1, 2])) == 3
assert len(permute_unique([1, 2, 3])) == 6      # সব আলাদা -> 3!
assert permute_unique([2, 2, 2]) == [[2, 2, 2]]  # সব সমান -> 1টা
assert permute_unique([1, 1]) == [[1, 1]]
assert len(permute_unique([1, 1, 2, 2])) == 6    # 4!/(2!·2!) = 6
print("সব test pass!")

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

nums.sort() — সমান মান পাশাপাশি, যাতে প্রতিবেশী-skip কাজ করে।
if len(path) == len(nums): — base case: পূর্ণ permutation।
if used[i]: continue — ব্যবহৃত index বাদ (Permutations থেকে)।
if i > 0 and nums[i]==nums[i-1] and not used[i-1]: continue — সমান copy-র ক্রম উল্টে যাওয়া রোধ; এটাই duplicate দমনের চাবি।
used[i]=True; path.append(nums[i]) — CHOOSE।
go(path) / path.pop(); used[i]=False — EXPLORE তারপর UN-CHOOSE।

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

permute_unique([1,1,2]): প্রথম slot-এ প্রথম 1 দিয়ে শাখা খোলে; দ্বিতীয় 1 (used[0]=False) skip হয়, তাই [1,...] শুরু একবারই; 2 দিয়ে [2,1,1]। ফল 3টা distinct। permutation-এ ভেতরের ক্রম জরুরি, তাই norm-এ শুধু বাইরের list sort করি (sorted-of-sorted নয়) — assert stable অথচ সঠিকতা যাচাই হয়। [2,2,2]-এ 1টা, [1,1,2,2]-এ 6টা। সব মিলে print: সব test pass!।

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

সময়¶

worst case O(n · n!) (সব আলাদা হলে) — distinct permutation যত, প্রতিটার snapshot নিতে n; duplicate থাকলে skip গাছ ছোট করে। sort-এর O(n log n) নিচে চাপা।

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

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

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

sort না করা — সমান মান ছড়িয়ে, প্রতিবেশী-skip ব্যর্থ, নকল ক্রম বেরোয়।
skip-শর্তে not used[i-1]-এর বদলে used[i-1] লেখা — উল্টো দিকে কাটে, বৈধ ক্রম হারায় (অনেকে এই version-ও use করে, কিন্তু তখন যুক্তিটা ভিন্ন; এই note-এ not used[i-1] ধরে রাখো)।
used flag reset (used[i]=False) ভুলে যাওয়া — পরের branch-এ item আটকে থাকে।
out.append(path) snapshot ছাড়া — সব entry একই live list-এর reference।

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

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

ভিত্তি: Permutations (এই tracker-এর #9)-এর choose-each-remaining + used, এখানে sort-and-skip যোগ করে। ../patterns.md-এর Pattern 4-এ Permutations II তালিকাভুক্ত; skip-এর ধারণা Pattern 3-এর Subsets II লাইন থেকে — শুধু branching factor "সব unused" হওয়ায় শর্তটা used[i-1] জড়িত।

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

Permutations (সব আলাদা) — https://leetcode.com/problems/permutations/ (এই tracker-এর #9)
Subsets II (sort-skip, subset) — https://leetcode.com/problems/subsets-ii/ (#10)
Creating Strings (CP-গতিতে একই idea) — https://cses.fi/problemset/task/1622/ (#18)

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

Choose-remaining + duplicate skip: Permutations-এর used-ভিত্তিক কঙ্কালে sort যোগ করো, তারপর nums[i]==nums[i-1] and not used[i-1] হলে skip — সমান copy-দের একটাই canonical ক্রমে বসিয়ে distinct ordering enumerate করার নিয়ম।

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

ভবিষ্যতের আমাকে: "Permutations II = Permutations + sort + skip-line nums[i]==nums[i-1] and not used[i-1]।" যখনই 'duplicate-সহ সব distinct ordering/arrangement' শুনবে — sort করে নাও, সমান copy-দের বাঁ-থেকে-ডান ক্রমে বসাও; এই not used[i-1] guard-টাই subsets-এর i>start skip-এর permutation-সংস্করণ।

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