সুষম বন্ধনী ক্রম#

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

$e$ (খালি স্ট্রিং) একটি সুষম বন্ধনী ক্রম।
যদি $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;
}