پرش به محتویات

تولید تمام ترکیب‌های Kتایی

در این مقاله به مسئله‌ی تولید تمام ترکیب‌های $K$تایی می‌پردازیم. با فرض دو عدد طبیعی $N$ و $K$ و با در نظر گرفتن مجموعه‌ای از اعداد ۱ تا $N$، هدف استخراج تمام زیرمجموعه‌هایی با اندازه‌ی $K$ است.

تولید ترکیب Kتایی بعدی از نظر لغت‌نامه‌ای

ابتدا آن‌ها را به ترتیب لغت‌نامه‌ای (lexicographical) تولید می‌کنیم. الگوریتم این کار ساده است. اولین ترکیب ${1, 2, ..., K}$ خواهد بود. حال ببینیم چگونه ترکیبی را که بلافاصله بعد از این ترکیب قرار می‌گیرد، پیدا کنیم. برای این کار، ترکیب فعلی خود را در نظر می‌گیریم و راست‌ترین عنصری را که هنوز به بالاترین مقدار ممکن خود نرسیده است، پیدا می‌کنیم. پس از پیدا کردن این عنصر، آن را ۱ واحد افزایش می‌دهیم و به تمام عناصر بعدی، کمترین مقدار معتبر را اختصاص می‌ده می‌دهیم.

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$تایی را به ترتیبی تولید کنیم که ترکیب‌های مجاور دقیقاً در یک عنصر با هم تفاوت داشته باشند.

این مسئله با استفاده از کد گری (Gray Code) قابل حل است: اگر به هر زیرمجموعه یک بیت‌ماسک (bitmask) اختصاص دهیم، با تولید و پیمایش این بیت‌ماسک‌ها با کدهای گری، می‌توانیم به پاسخ برسیم.

مسئله‌ی تولید ترکیب‌های $K$تایی را می‌توان با استفاده از کدهای گری به روش دیگری نیز حل کرد: کدهای گری را برای اعداد ۰ تا $2^N - 1$ تولید کرده و فقط کدهایی را که شامل $K$ یک هستند، نگه می‌داریم. نکته‌ی جالب این است که در دنباله‌ی حاصل از بیت‌ماسک‌هایی با $K$ بیت یک، هر دو ماسک مجاور (شامل ماسک اول و آخر - مجاورت به صورت چرخشی) دقیقاً در دو بیت تفاوت خواهند داشت، که این همان هدف ماست (حذف یک عدد، اضافه کردن یک عدد).

بیایید این موضوع را اثبات کنیم:

برای اثبات، این واقعیت را یادآوری می‌کنیم که دنباله‌ی $G(N)$ (که نشان‌دهنده‌ی کدهای گری برای $N$ بیت است) را می‌توان به صورت زیر به دست آورد:

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

یعنی، دنباله‌ی کد گری برای $N-1$ را در نظر بگیرید و به ابتدای هر عضو آن، پیشوند ۰ اضافه کنید. سپس دنباله‌ی معکوس کد گری برای $N-1$ را در نظر گرفته و به ابتدای هر ماسک آن، پیشوند ۱ اضافه کنید و این دو دنباله را به هم بچسبانید.

اکنون می‌توانیم اثبات خود را ارائه دهیم.

ابتدا اثبات می‌کنیم که ماسک‌های اول و آخر دقیقاً در دو بیت تفاوت دارند. برای این کار، کافی است توجه داشته باشیم که اولین ماسک در دنباله‌ی $G(N)$ (که $K$ بیت یک دارد) به شکل $N-K$ صفر و به دنبال آن $K$ یک خواهد بود. از آنجا که بیت اول ۰ است، به دنبال آن $(N-K-1)$ صفر و سپس $K$ بیت یک می‌آید. ماسک آخر نیز به شکل ۱، سپس $(N-K)$ صفر و بعد $K-1$ یک خواهد بود. با به کار بردن اصل استقرای ریاضی و استفاده از فرمول $G(N)$، اثبات به پایان می‌رسد.

حال وظیفه‌ی ما این است که نشان دهیم هر دو کد مجاور نیز دقیقاً در دو بیت تفاوت دارند. این کار را می‌توانیم با در نظر گرفتن معادله‌ی بازگشتی برای تولید کدهای گری انجام دهیم. فرض کنیم محتوای دو نیمه‌ی تشکیل شده توسط $G(N-1)$ درست است. اکنون باید ثابت کنیم که زوج متوالی جدیدی که در محل اتصال (با الحاق این دو نیمه) تشکیل می‌شود نیز معتبر است، یعنی دقیقاً در دو بیت تفاوت دارند.

این کار امکان‌پذیر است، زیرا ما ماسک آخرِ نیمه‌ی اول و ماسک اولِ نیمه‌ی دوم را می‌دانیم. آخرین ماسکِ نیمه‌ی اول به صورت ۱، سپس $(N-K-1)$ صفر و بعد از آن $K-1$ یک خواهد بود. و اولین ماسکِ نیمه‌ی دوم به صورت ۰، سپس $(N-K-2)$ صفر و به دنبال آن $K$ یک خواهد بود. بنابراین، با مقایسه‌ی این دو ماسک، دقیقاً دو بیتِ متفاوت پیدا می‌کنیم.

در ادامه یک پیاده‌سازی ساده (naive) آمده است که با تولید تمام $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);
}