সব $K$-কম্বিনেশন জেনারেট করা#

এই আর্টিকেলে আমরা সব $K$-কম্বিনেশন জেনারেট করার সমস্যা আলোচনা করব। প্রাকৃতিক সংখ্যা $N$ এবং $K$ দেওয়া আছে, এবং $1$ থেকে $N$ পর্যন্ত সংখ্যার একটি সেট কনসিডার করা হচ্ছে। কাজ হলো $K$ আকারের সব সাবসেট বের করা।

পরবর্তী লেক্সিকোগ্রাফিক্যাল $K$-কম্বিনেশন জেনারেট করা#

প্রথমে আমরা লেক্সিকোগ্রাফিক্যাল ক্রমে জেনারেট করব। এর জন্য অ্যালগরিদমটি সরল। প্রথম কম্বিনেশন হবে ${1, 2, ..., K}$। এখন দেখা যাক কীভাবে এর ঠিক পরের লেক্সিকোগ্রাফিক্যাল কম্বিনেশন খুঁজে পাওয়া যায়। এর জন্য, আমরা আমাদের বর্তমান কম্বিনেশন কনসিডার করি এবং সবচেয়ে ডানদিকের সেই উপাদানটি খুঁজি যেটাএখনও তার সর্বোচ্চ সম্ভাব্য মানে পৌঁছায়নি। এই উপাদানটি পাওয়ার পর, আমরা এটা$1$ বাড়াই এবং পরবর্তী সব উপাদানে সবচেয়ে ছোট বৈধ মান বসাই।

bool next_combination(vector<int>& a, int n) {
    int k = (int)a.size();
    for (int i = k - 1; i >= 0; i--) {
        if (a[i] < n - k + i + 1) {
            a[i]++;
            for (int j = i + 1; j < k; j++)
                a[j] = a[j - 1] + 1;
            return true;
        }
    }
    return false;
}

এমন সব $K$-কম্বিনেশন জেনারেট করা যেখানে পাশাপাশি কম্বিনেশনগুলো একটি উপাদানে ভিন্ন#

এবার আমরা এমনভাবে সব $K$-কম্বিনেশন জেনারেট করতে চাই যেন পাশাপাশি কম্বিনেশনগুলো ঠিক একটি উপাদানে ভিন্ন হয়।

এটাগ্রে কোড ব্যবহার করে সমাধান করা যায়: যদি আমরা প্রতিটি সাবসেটে একটি বিটমাস্ক বসাই, তাহলে গ্রে কোড দিয়ে এই বিটমাস্কগুলো জেনারেট এবং ইটারেট করে আমরা আমাদের উত্তর পেতে পারি।

$K$-কম্বিনেশন জেনারেট করার কাজটি গ্রে কোড ব্যবহার করে ভিন্নভাবেও সমাধান করা যায়: $0$ থেকে $2^N - 1$ পর্যন্ত সংখ্যার জন্য গ্রে কোড জেনারেট করো এবং শুধু সেই কোডগুলো রাখো যেগুলোতে $K$টি $1$ আছে। বিস্ময়কর তথ্য হলো $K$টি সেট বিট বিশিষ্ট ফলাফল ক্রমে, যেকোনো দুটি প্রতিবেশী মাস্ক (প্রথম এবং শেষ মাস্ক সহ — চক্রীয় অর্থে প্রতিবেশী) — ঠিক দুটি বিটে ভিন্ন হবে, যা আমাদের উদ্দেশ্য (একটি সংখ্যা সরাও, একটি সংখ্যা যোগ করো)।

এটাপ্রুফ করা যাক:

প্রুফের জন্য, আমরা স্মরণ করি যে $G(N)$ ক্রম ($N$-তম গ্রে কোড উপস্থাপন করে) এভাবে পাওয়া যায়:

$$G(N) = 0G(N-1) \cup 1G(N-1)^\text{R}$$

অর্থাৎ, $N-1$-এর জন্য গ্রে কোড ক্রম কনসিডার করো এবং প্রতিটি পদের আগে $0$ বসাও। এবং $N-1$-এর বিপরীত গ্রে কোড ক্রম কনসিডার করো এবং প্রতিটি মাস্কের আগে $1$ বসাও, তারপর এই দুটি ক্রম সংযুক্ত করো।

এখন আমরা প্রুফ করতে পারি।

প্রথমে, আমরা প্রুফ করি যে প্রথম এবং শেষ মাস্ক ঠিক দুটি বিটে ভিন্ন। এটাকরতে, লক্ষ্য করাই যথেষ্ট যে $G(N)$ ক্রমের প্রথম মাস্কটি হবে $N-K$টি $0$, তারপর $K$টি $1$। যেহেতু প্রথম বিটটি $0$ হিসেবে সেট করা, তারপর $(N-K-1)$টি $0$, তারপর $K$টি সেট বিট আসে এবং শেষ মাস্কটি হবে $1$, তারপর $(N-K)$টি $0$, তারপর $K-1$টি $1$। ম্যাথমেটিক্যাল ইন্ডাকশন নীতি প্রয়োগ করে এবং $G(N)$-এর সূত্র ব্যবহার করে প্রুফ সম্পূর্ণ হয়।

এখন আমাদের কাজ দেখানো যে যেকোনো দুটি পাশাপাশি কোডও ঠিক দুটি বিটে ভিন্ন, আমরা গ্রে কোড জেনারেশনের রিকার্সিভ ইকুয়েশন কনসিডার করে এটাকরতে পারি। ধরে নিই $G(N-1)$ দ্বারা গঠিত দুই অংশের বিষয়বস্তু সত্য। এখন আমাদের প্রুফ করতে হবে যে জংশনে (এই দুই অংশের সংযোগস্থলে) গঠিত নতুন পরপর জোড়াটিও বৈধ, অর্থাৎ তারা ঠিক দুটি বিটে ভিন্ন।

এটাকরা যায়, কারণ আমরা জানি প্রথম অর্ধের শেষ মাস্ক এবং দ্বিতীয় অর্ধের প্রথম মাস্ক। প্রথম অর্ধের শেষ মাস্ক হবে $1$, তারপর $(N-K-1)$টি $0$, তারপর $K-1$টি $1$। এবং দ্বিতীয় অর্ধের প্রথম মাস্ক হবে $0$, তারপর $(N-K-2)$টি $0$, তারপর $K$টি $1$। তাই দুটি মাস্ক তুলনা করলে আমরা ঠিক দুটি ভিন্ন বিট পাই।

নিচে একটি সহজ ইমপ্লিমেন্টেশন দেওয়া হলো যা সব $2^{n}$ সম্ভাব্য সাবসেট জেনারেট করে এবং $K$ আকারের সাবসেটগুলো খুঁজে বের করে কাজ করে।

int gray_code (int n) {
    return n ^ (n >> 1);
}

int count_bits (int n) {
    int res = 0;
    for (; n; n >>= 1)
        res += n & 1;
    return res;
}

void all_combinations (int n, int k) {
    for (int i = 0; i < (1 << n); i++) {
        int cur = gray_code (i);
        if (count_bits(cur) == k) {
            for (int j = 0; j < n; j++) {
                if (cur & (1 << j))
                    cout << j + 1;
            }
            cout << "\n";
        }
    }
}

উল্লেখ্য যে একটি আরও কার্যকর ইমপ্লিমেন্টেশন আছে যা শুধুমাত্র বৈধ কম্বিনেশন তৈরি করে এবং তাই $O\left(N \cdot \binom{N}{K}\right)$-এ কাজ করে, তবে এটাপ্রকৃতিতে রিকার্সিভ এবং $N$-এর ছোট মানের জন্য সম্ভবত আগের সমাধানের চেয়ে বড় ধ্রুবক আছে।

ইমপ্লিমেন্টেশনটি সূত্র থেকে প্রাপ্ত:

$$G(N, K) = 0G(N-1, K) \cup 1G(N-1, K-1)^\text{R}$$

এই সূত্রটি সাধারণ গ্রে কোড ডিটারমিনের ইকুয়েশন পরিবর্তন করে পাওয়া যায়, এবং উপযুক্ত উপাদান থেকে সাবসিকোয়েন্স নির্বাচন করে কাজ করে।

এর ইমপ্লিমেন্টেশন এরকম:

vector<int> ans;

void gen(int n, int k, int idx, bool rev) {
    if (k > n || k < 0)
        return;

    if (!n) {
        for (int i = 0; i < idx; ++i) {
            if (ans[i])
                cout << i + 1;
        }
        cout << "\n";
        return;
    }

    ans[idx] = rev;
    gen(n - 1, k - rev, idx + 1, false);
    ans[idx] = !rev;
    gen(n - 1, k - !rev, idx + 1, true);
}

void all_combinations(int n, int k) {
    ans.resize(n);
    gen(n, k, 0, false);
}