Bagaimanakah Saya Boleh Menjana Gabungan dengan Cekap dalam C Menggunakan Manipulasi Bit?

Menjana Gabungan dalam C : Penyelesaian Komprehensif

Menjana gabungan ialah tugas pengaturcaraan asas yang melibatkan pemilihan bilangan elemen tertentu daripada set . Sebagai contoh, jika kita mempunyai set S = {1, 2, 3, 4, 5} dan kita ingin menghasilkan kombinasi saiz r = 2, output akan termasuk gabungan seperti (1, 2), (1, 3 ), (2, 3), dan seterusnya.

Satu cara berkesan untuk menjana kombinasi menggunakan C ialah dengan menggunakan manipulasi bit. Kita boleh memulakan vektor boolean panjang n, mewakili elemen set, dan kemudian mengisi elemen r pertama dengan benar. Ini menandakan elemen yang sepadan dipilih dalam gabungan semasa.

Langkah seterusnya ialah mencipta semua pilih atur vektor pemilihan ini menggunakan fungsi std::next_permutation. Untuk setiap pilih atur, kami menyemak sama ada elemen dipilih (ditunjukkan oleh nilai sebenar dalam vektor) dan mencetak elemen yang sepadan. Dengan mengulangi semua pilih atur, kami boleh menjana semua kombinasi yang mungkin.

Berikut ialah coretan kod menggunakan pendekatan ini:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int n, r;
    std::cin >> n;
    std::cin >> r;

    std::vector<bool> v(n);
    std::fill(v.end() - r, v.end(), true);

    do {
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                std::cout << (i + 1) << " ";
            }
        }
        std::cout << "\n";
    } while (std::next_permutation(v.begin(), v.end()));
    return 0;
}

Sebagai alternatif, kita boleh menggunakan fungsi std::prev_permutation untuk menjana gabungan dalam tertib menaik:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
   int n, r;
   std::cin >> n;
   std::cin >> r;

   std::vector<bool> v(n);
   std::fill(v.begin(), v.begin() + r, true);

   do {
       for (int i = 0; i < n; ++i) {
           if (v[i]) {
               std::cout << (i + 1) << " ";
           }
       }
       std::cout << "\n";
   } while (std::prev_permutation(v.begin(), v.end()));
   return 0;
}

Dengan menggunakan teknik ini, kita boleh menjana kombinasi dengan cekap dalam C , menyediakan alat yang berkuasa untuk pelbagai aplikasi algoritma.

Atas ialah kandungan terperinci Bagaimanakah Saya Boleh Menjana Gabungan dengan Cekap dalam C Menggunakan Manipulasi Bit?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!