সব $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);
}