ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স (Balanced Bracket Sequences)#

একটি ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স হলো শুধুমাত্র ব্র্যাকেট দিয়ে গঠিত একটি স্ট্রিং, যেখানে এই ক্রমে নির্দিষ্ট সংখ্যা ও গাণিতিক অপারেশন বসালে একটি বৈধ গাণিতিক রাশি পাওয়া যায়। ফর্মালি ব্যালেন্সড ব্র্যাকেট সিকোয়েন্সকে এভাবে ডিফাইন করা যায়:

$e$ (empty string) একটি ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স।
যদি $s$ একটি ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স হয়, তাহলে $(s)$-ও একটি ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স।
যদি $s$ এবং $t$ ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স হয়, তাহলে $s t$-ও একটি ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স।

উদাহরণস্বরূপ $(())()$ একটি ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স, কিন্তু $())($ নয়।

অবশ্যই একইভাবে একাধিক ধরনের ব্র্যাকেট দিয়েও অন্যান্য ব্র্যাকেট ক্রম ডিফাইন করা যায়।

এই আর্টিকেলে আমরা ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স সম্পর্কিত কিছু ক্লাসিক সমস্যা আলোচনা করবো (সরলতার জন্য আমরা এদের শুধু ক্রম বলবো): বৈধতা যাচাই, ক্রমের সংখ্যা, লেক্সিকোগ্রাফিক্যালি পরবর্তী ক্রম খোঁজা, একটি নির্দিষ্ট দৈর্ঘ্যের সব ক্রম তৈরি, ক্রমের ইনডেক্স বের করা, এবং $k$-তম ক্রম তৈরি করা। আমরা সমস্যাগুলোর দুটি রূপও আলোচনা করবো, সরলতর সংস্করণ যেখানে শুধু একটি ধরনের ব্র্যাকেট অনুমোদিত, এবং কঠিনতর ক্ষেত্র যেখানে একাধিক ধরনের ব্র্যাকেট আছে।

ভ্যালিডিটি যাচাই#

আমরা পরীক্ষা করতে চাই একটি দেওয়া স্ট্রিং ব্যালেন্সড কিনা।

প্রথমে ধরি শুধু একটি ধরনের ব্র্যাকেট আছে। এই ক্ষেত্রে একটি অত্যন্ত সরল অ্যালগরিদম আছে। ধরি $\text{depth}$ হলো বর্তমান খোলা ব্র্যাকেটের সংখ্যা। শুরুতে $\text{depth} = 0$। আমরা স্ট্রিংয়ের সব ক্যারেক্টারের মধ্য দিয়ে যাবো, যদি বর্তমান ব্র্যাকেট ক্যারেক্টারটি একটি খোলা ব্র্যাকেট হয়, তাহলে আমরা $\text{depth}$ বাড়াবো, অন্যথায় কমাবো। যদি কোনো সময়ে $\text{depth}$ ভেরিয়েবল ঋণাত্মক হয়ে যায়, অথবা শেষে এটা$0$ থেকে ভিন্ন হয়, তাহলে স্ট্রিংটি ব্যালেন্সড সিকোয়েন্স নয়। অন্যথায় এটাব্যালেন্সড।

যদি একাধিক ধরনের ব্র্যাকেট থাকে, তাহলে অ্যালগরিদম পরিবর্তন করতে হবে। $\text{depth}$ কাউন্টারের পরিবর্তে আমরা একটি স্ট্যাক তৈরি করি, যেখানে আমরা সব পাওয়া খোলা ব্র্যাকেট সংরক্ষণ করবো। যদি বর্তমান ব্র্যাকেট ক্যারেক্টারটি খোলা হয়, আমরা একে স্ট্যাকে রাখি। যদি এটাবন্ধ হয়, তাহলে আমরা পরীক্ষা করি স্ট্যাক খালি কিনা, এবং স্ট্যাকের শীর্ষ উপাদান বর্তমান বন্ধ ব্র্যাকেটের একই ধরনের কিনা। যদি উভয় শর্ত পূরণ হয়, তাহলে আমরা স্ট্যাক থেকে খোলা ব্র্যাকেটটি সরিয়ে ফেলি। যদি কোনো সময়ে কোনো একটি শর্ত পূরণ না হয়, অথবা শেষে স্ট্যাক খালি না থাকে, তাহলে স্ট্রিংটি ব্যালেন্সড নয়। অন্যথায় এটাব্যালেন্সড।

ব্যালেন্সড সিকোয়েন্সের সংখ্যা#

সূত্র#

শুধু একটি ধরনের ব্র্যাকেট দিয়ে ব্যালেন্সড ব্র্যাকেট সিকোয়েন্সের সংখ্যা ক্যাটালান সংখ্যা ব্যবহার করে গণনা করা যায়। দৈর্ঘ্য $2n$ ($n$ জোড়া ব্র্যাকেট) এর ব্যালেন্সড ব্র্যাকেট সিকোয়েন্সের সংখ্যা হলো:

$$\frac{1}{n+1} \binom{2n}{n}$$

যদি আমরা $k$ ধরনের ব্র্যাকেট অনুমোদন করি, তাহলে প্রতিটি জোড়া $k$ ধরনের যেকোনো একটি হতে পারে (অন্যগুলো থেকে স্বাধীনভাবে), সুতরাং ব্যালেন্সড ব্র্যাকেট সিকোয়েন্সের সংখ্যা হলো:

$$\frac{1}{n+1} \binom{2n}{n} k^n$$

ডায়নামিক প্রোগ্রামিং#

অন্যদিকে এই সংখ্যাগুলো ডায়নামিক প্রোগ্রামিং ব্যবহার করেও গণনা করা যায়। ধরি $d[n]$ হলো $n$ জোড়া ব্র্যাকেট দিয়ে ব্যালেন্সড ব্র্যাকেট সিকোয়েন্সের সংখ্যা। লক্ষ্য করো প্রথম অবস্থানে সবসময় একটি খোলা ব্র্যাকেট থাকে। এবং পরে কোথাও এই জোড়ার সংশ্লিষ্ট বন্ধ ব্র্যাকেট আছে। এটা স্পষ্ট যে এই জোড়ার ভেতরে একটি ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স আছে, এবং একইভাবে এই জোড়ার পরেও একটি ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স আছে। সুতরাং $d[n]$ গণনা করতে, আমরা দেখবো প্রথম ব্র্যাকেট জোড়ার ভেতরে $i$ জোড়া ব্র্যাকেটের কতগুলো ব্যালেন্সড সিকোয়েন্স আছে, এবং এই জোড়ার পরে $n-1-i$ জোড়ার কতগুলো ব্যালেন্সড সিকোয়েন্স আছে। ফলে সূত্রটি হলো:

$$d[n] = \sum_{i=0}^{n-1} d[i] \cdot d[n-1-i]$$

এই রিকার্শনের প্রাথমিক মান $d[0] = 1$।

লেক্সিকোগ্রাফিক্যালি পরবর্তী ব্যালেন্সড সিকোয়েন্স খোঁজা#

এখানে আমরা শুধু একটি বৈধ ব্র্যাকেট ধরনের ক্ষেত্র কনসিডার করবো।

একটি ব্যালেন্সড সিকোয়েন্স দেওয়া আছে, আমাদের পরবর্তী (লেক্সিকোগ্রাফিক্যালি) ব্যালেন্সড সিকোয়েন্সটি খুঁজে বের করতে হবে।

এটা স্পষ্ট হওয়া উচিত যে আমাদের সবচেয়ে ডানের খোলা ব্র্যাকেটটি খুঁজতে হবে, যাকে আমরা একটি বন্ধ ব্র্যাকেট দিয়ে প্রতিস্থাপন করতে পারি এই শর্ত ভঙ্গ না করে যে এই অবস্থান পর্যন্ত খোলা ব্র্যাকেটের চেয়ে বেশি বন্ধ ব্র্যাকেট নেই। এই অবস্থান প্রতিস্থাপনের পর, বাকি অংশটি লেক্সিকোগ্রাফিক্যালি ক্ষুদ্রতম দিয়ে পূরণ করা যায়: অর্থাৎ প্রথমে যতগুলো সম্ভব খোলা ব্র্যাকেট দিয়ে, এবং তারপর বাকি অবস্থানগুলো বন্ধ ব্র্যাকেট দিয়ে পূরণ করা। অন্যভাবে বলতে গেলে আমরা যতদূর সম্ভব দীর্ঘ প্রিফিক্স অপরিবর্তিত রাখার চেষ্টা করি, এবং সাফিক্সটি লেক্সিকোগ্রাফিক্যালি ক্ষুদ্রতম দিয়ে প্রতিস্থাপিত হয়।

এই অবস্থান খুঁজতে, আমরা ডান থেকে বামে ক্যারেক্টারগুলো দেখবো, এবং খোলা ও বন্ধ ব্র্যাকেটের ভারসাম্য $\text{depth}$ বজায় রাখবো। যখন আমরা বন্ধ ব্র্যাকেট পাই, $\text{depth}$ বাড়াবো, এবং যখন খোলা ব্র্যাকেট পাই, কমাবো। যদি কোনো একটি স্থানে আমরা একটি খোলা ব্র্যাকেট পাই, এবং এই চিহ্ন প্রক্রিয়া করার পর ভারসাম্য ধনাত্মক হয়, তাহলে আমরা সবচেয়ে ডানের সেই অবস্থানটি পেয়ে গেছি যা পরিবর্তন করা যায়। আমরা চিহ্নটি পরিবর্তন করি, ডান দিকে কতগুলো খোলা ও বন্ধ ব্র্যাকেট যোগ করতে হবে তা গণনা করি, এবং লেক্সিকোগ্রাফিক্যালি ক্ষুদ্রতম উপায়ে সাজাই।

যদি উপযুক্ত কোনো অবস্থান না পাওয়া যায়, তাহলে এই ক্রমটি ইতিমধ্যেই সর্বোচ্চ সম্ভব, এবং কোনো উত্তর নেই।

bool next_balanced_sequence(string & s) {
    int n = s.size();
    int depth = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '(')
            depth--;
        else
            depth++;

        if (s[i] == '(' && depth > 0) {
            depth--;
            int open = (n - i - 1 - depth) / 2;
            int close = n - i - 1 - open;
            string next = s.substr(0, i) + ')' + string(open, '(') + string(close, ')');
            s.swap(next);
            return true;
        }
    }
    return false;
}

এই ফাংশনটি $O(n)$ সময়ে পরবর্তী ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স গণনা করে, এবং পরবর্তী না থাকলে false রিটার্ন করে।

সব ব্যালেন্সড সিকোয়েন্স খোঁজা#

কখনো কখনো নির্দিষ্ট দৈর্ঘ্য $n$ এর সব ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স খুঁজে বের করে আউটপুট করতে হয়।

এগুলো তৈরি করতে, আমরা লেক্সিকোগ্রাফিক্যালি ক্ষুদ্রতম ক্রম $((\dots(())\dots))$ দিয়ে শুরু করতে পারি, এবং তারপর আগের সেকশনে দেখানো অ্যালগরিদম দিয়ে পরবর্তী লেক্সিকোগ্রাফিক্যালির ক্রমগুলো খুঁজতে থাকি।

তবে, যদি ক্রমের দৈর্ঘ্য খুব বেশি না হয় (যেমন $n$ ১২ এর চেয়ে ছোট), তাহলে আমরা C++ STL ফাংশন next_permutation দিয়ে সুবিধাজনকভাবে সব পারমুটেশন তৈরি করতে পারি, এবং প্রতিটির ভ্যালিডিটি পরীক্ষা করতে পারি।

এছাড়াও ডায়নামিক প্রোগ্রামিং দিয়ে সব ক্রম গণনার জন্য যে ধারণা ব্যবহার করেছি সেগুলো দিয়েও তৈরি করা যায়। আমরা পরবর্তী দুটি বিভাগে এই ধারণাগুলো আলোচনা করবো।

ক্রমের ইনডেক্স#

$n$ জোড়া ব্র্যাকেটের একটি ব্যালেন্সড ব্র্যাকেট সিকোয়েন্স দেওয়া আছে। $n$ জোড়া ব্র্যাকেটের সব ব্যালেন্সড সিকোয়েন্সের লেক্সিকোগ্রাফিক্যালি সাজানো তালিকায় এর ইনডেক্স বের করতে হবে।

একটি সহায়ক অ্যারে $d[i][j]$ ডিফাইন করি, যেখানে $i$ হলো ব্র্যাকেট ক্রমের দৈর্ঘ্য (আধা-ব্যালেন্সড, প্রতিটি বন্ধ ব্র্যাকেটের একটি সংশ্লিষ্ট খোলা ব্র্যাকেট আছে, কিন্তু প্রতিটি খোলা ব্র্যাকেটের অবশ্যই একটি সংশ্লিষ্ট বন্ধ ব্র্যাকেট নেই), এবং $j$ হলো বর্তমান ভারসাম্য (খোলা ও বন্ধ ব্র্যাকেটের পার্থক্য)। $d[i][j]$ হলো এই প্যারামিটারের সাথে মেলে এমন ক্রমের সংখ্যা। আমরা শুধু একটি ব্র্যাকেট ধরন দিয়ে এই সংখ্যাগুলো গণনা করবো।

$i = 0$ এর প্রারম্ভিক মানের জন্য উত্তর স্পষ্ট: $d[0][0] = 1$, এবং $j > 0$ এর জন্য $d[0][j] = 0$। এখন ধরি $i > 0$, এবং আমরা ক্রমের শেষ ক্যারেক্টারটি দেখি। শেষ ক্যারেক্টার যদি খোলা ব্র্যাকেট $($ হয়, তাহলে আগের অবস্থা ছিল $(i-1, j-1)$, যদি বন্ধ ব্র্যাকেট $)$ হয়, তাহলে আগের অবস্থা ছিল $(i-1, j+1)$। সুতরাং আমরা রিকারেন্স রিলেশন পাই:

$$d[i][j] = d[i-1][j-1] + d[i-1][j+1]$$

ঋণাত্মক $j$ এর জন্য $d[i][j] = 0$ স্পষ্টতই সত্য। সুতরাং আমরা এই অ্যারে $O(n^2)$-এ গণনা করতে পারি।

এখন একটি দেওয়া ক্রমের ইনডেক্স তৈরি করা যাক।

প্রথমে ধরি শুধু একটি ধরনের ব্র্যাকেট আছে। আমরা $\text{depth}$ কাউন্টার ব্যবহার করবো যা বলে আমরা বর্তমানে কত গভীরে আছি, এবং ক্রমের ক্যারেক্টারগুলো দেখবো। যদি বর্তমান ক্যারেক্টার $s[i]$ $($ এর সমান হয়, তাহলে আমরা $\text{depth}$ বাড়াই। যদি বর্তমান ক্যারেক্টার $s[i]$ $)$ এর সমান হয়, তাহলে আমাদের $d[2n-i-1][\text{depth}+1]$ উত্তরে যোগ করতে হবে, $($ দিয়ে শুরু হওয়া সব সম্ভব শেষ কনসিডার করে নিয়ে (যেগুলো লেক্সিকোগ্রাফিক্যালি ছোট ক্রম), এবং তারপর $\text{depth}$ কমাই।

এখন ধরি $k$ ভিন্ন ধরনের ব্র্যাকেট আছে।

সুতরাং, যখন আমরা বর্তমান ক্যারেক্টার $s[i]$ দেখি $\text{depth}$ পুনঃগণনার আগে, আমাদের বর্তমান ক্যারেক্টারের চেয়ে ছোট সব ব্র্যাকেট ধরন দেখতে হবে, এবং বর্তমান অবস্থানে এই ব্র্যাকেট বসানোর চেষ্টা করতে হবে (নতুন ভারসাম্য $\text{ndepth} = \text{depth} \pm 1$ পেয়ে), এবং ক্রম সম্পূর্ণ করার উপায়ের সংখ্যা (দৈর্ঘ্য $2n-i-1$, ভারসাম্য $ndepth$) উত্তরে যোগ করতে হবে:

$$d[2n - i - 1][\text{ndepth}] \cdot k^{\frac{2n - i - 1 - ndepth}{2}}$$

এই সূত্রটা এভাবে বের করা যায়: প্রথমে আমরা “ভুলে যাই” যে একাধিক ব্র্যাকেট ধরন আছে, এবং শুধু উত্তর $d[2n - i - 1][\text{ndepth}]$ নিই। এখন কনসিডার করি $k$ ধরনের ব্র্যাকেট থাকলে উত্তর কীভাবে পরিবর্তন হবে। আমাদের $2n - i - 1$ টি অনির্ধারিত অবস্থান আছে, যার মধ্যে $\text{ndepth}$ টি ইতিমধ্যে খোলা ব্র্যাকেট দ্বারা পূর্বনির্ধারিত। কিন্তু বাকি সব ব্র্যাকেট ($(2n - i - 1 - \text{ndepth})/2$ জোড়া) যেকোনো ধরনের হতে পারে, তাই আমরা সংখ্যাটিকে $k$ এর এরকম একটি ঘাত দিয়ে গুণ করি।

$k$-তম ক্রম খোঁজা#

ধরি $n$ হলো ক্রমে ব্র্যাকেট জোড়ার সংখ্যা। একটি দেওয়া $k$ এর জন্য সব ব্যালেন্সড সিকোয়েন্সের লেক্সিকোগ্রাফিক্যালি সাজানো তালিকায় $k$-তম ব্যালেন্সড সিকোয়েন্স খুঁজতে হবে।

আগের সেকশনের মতো আমরা সহায়ক অ্যারে $d[i][j]$ গণনা করি, দৈর্ঘ্য $i$ ও ভারসাম্য $j$ এর আধা-ব্যালেন্সড ব্র্যাকেট সিকোয়েন্সের সংখ্যা।

প্রথমে, শুধু একটি ব্র্যাকেট ধরন দিয়ে শুরু করি।

আমরা যে স্ট্রিং তৈরি করতে চাই তার ক্যারেক্টারগুলোর মধ্য দিয়ে যাবো। আগের সমস্যার মতো আমরা $\text{depth}$ কাউন্টার সংরক্ষণ করি, বর্তমান নেস্টিং গভীরতা। প্রতিটি অবস্থানে, আমাদের সিদ্ধান্ত নিতে হবে খোলা ব্র্যাকেট বসাবো নাকি বন্ধ ব্র্যাকেট। খোলা ব্র্যাকেট বসাতে, $d[2n - i - 1][\text{depth}+1] \ge k$ সত্য হতে হবে। যদি তাই হয়, আমরা $\text{depth}$ কাউন্টার বাড়াই, এবং পরবর্তী ক্যারেক্টারে যাই। অন্যথায়, আমরা $d[2n - i - 1][\text{depth}+1]$ থেকে $k$ কমাই, একটি বন্ধ ব্র্যাকেট বসাই, এবং এগিয়ে যাই।

string kth_balanced(int n, int k) {
    vector<vector<int>> d(2*n+1, vector<int>(n+1, 0));
    d[0][0] = 1;
    for (int i = 1; i <= 2*n; i++) {
        d[i][0] = d[i-1][1];
        for (int j = 1; j < n; j++)
            d[i][j] = d[i-1][j-1] + d[i-1][j+1];
        d[i][n] = d[i-1][n-1];
    }

    string ans;
    int depth = 0;
    for (int i = 0; i < 2*n; i++) {
        if (depth + 1 <= n && d[2*n-i-1][depth+1] >= k) {
            ans += '(';
            depth++;
        } else {
            ans += ')';
            if (depth + 1 <= n)
                k -= d[2*n-i-1][depth+1];
            depth--;
        }
    }
    return ans;
}

এখন ধরি $k$ ধরনের ব্র্যাকেট আছে। সমাধান শুধু সামান্য পার্থক্য রাখবে এই দিক থেকে যে আমাদের $d[2n-i-1][\text{ndepth}]$ মানকে $k^{(2n-i-1-\text{ndepth})/2}$ দিয়ে গুণ করতে হবে এবং কনসিডার করে রাখতে হবে যে পরবর্তী ক্যারেক্টারের জন্য বিভিন্ন ব্র্যাকেট ধরন হতে পারে।

এখানে দুটি ধরনের ব্র্যাকেট ব্যবহার করে একটি ইমপ্লিমেন্টেশন: গোল এবং চৌকো:

string kth_balanced2(int n, int k) {
    vector<vector<int>> d(2*n+1, vector<int>(n+1, 0));
    d[0][0] = 1;
    for (int i = 1; i <= 2*n; i++) {
        d[i][0] = d[i-1][1];
        for (int j = 1; j < n; j++)
            d[i][j] = d[i-1][j-1] + d[i-1][j+1];
        d[i][n] = d[i-1][n-1];
    }

    string ans;
    int shift, depth = 0;

    stack<char> st;
    for (int i = 0; i < 2*n; i++) {

        // '('
        shift = ((2*n-i-1-depth-1) / 2);
        if (shift >= 0 && depth + 1 <= n) {
            int cnt = d[2*n-i-1][depth+1] << shift;
            if (cnt >= k) {
                ans += '(';
                st.push('(');
                depth++;
                continue;
            }
            k -= cnt;
        }

        // ')'
        shift = ((2*n-i-1-depth+1) / 2);
        if (shift >= 0 && depth && st.top() == '(') {
            int cnt = d[2*n-i-1][depth-1] << shift;
            if (cnt >= k) {
                ans += ')';
                st.pop();
                depth--;
                continue;
            }
            k -= cnt;
        }

        // '['
        shift = ((2*n-i-1-depth-1) / 2);
        if (shift >= 0 && depth + 1 <= n) {
            int cnt = d[2*n-i-1][depth+1] << shift;
            if (cnt >= k) {
                ans += '[';
                st.push('[');
                depth++;
                continue;
            }
            k -= cnt;
        }

        // ']'
        ans += ']';
        st.pop();
        depth--;
    }
    return ans;
}