Bagaimanakah C \'s `std::next_permutation` Boleh Digunakan untuk Menjana Semua Gabungan Saiz Tertentu?

Menjana Gabungan dalam C

Mencipta gabungan melibatkan pemilihan subset elemen daripada set tertentu tanpa mengambil kira susunan pilihan. Apabila berhadapan dengan tugas menjana kombinasi menggunakan C , adalah penting untuk mempertimbangkan perkara berikut:

Definisi Masalah:

Diberi set S = {1, 2, 3 , ..., n} dan nilai r, dengan r ialah bilangan elemen yang akan dipilih daripada set, kami menyasarkan untuk menjana semua kemungkinan kombinasi panjang r daripada yang diberikan set.

Pendekatan Penyelesaian:

Satu pendekatan untuk menyelesaikan masalah ini ialah dengan menggunakan fungsi std::next_permutation daripada Perpustakaan Standard C. Fungsi ini membolehkan kami menjana semua pilih atur bagi vektor unsur. Dengan menggunakan fungsi ini, kita boleh mencipta vektor nilai boolean yang mewakili elemen yang dipilih.

Pelaksanaan:

Berikut ialah contoh pelaksanaan menggunakan std::next_permutation:

#include <iostream>
#include <vector>

int main() {
    int n, r;
    std::cin >> n >> 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;
}

Dalam pelaksanaan ini, kami mencipta vektor dengan panjang n dan mengisi elemen r terakhir dengan benar. Fungsi std::next_permutation kemudiannya digunakan untuk menjana semua pilih atur yang mungkin bagi vektor. Untuk setiap pilih atur, kami mencetak elemen yang sepadan dengan nilai sebenar dalam vektor.

Penjelasan:

Pendekatan ini berfungsi dengan mencipta "tatasusunan pilihan" (v) di mana kita meletakkan pemilih r. Kami kemudian menjana semua pilih atur pemilih ini dan mencetak ahli set yang sepadan jika mereka dipilih dalam pilih atur semasa v.

Dengan menggunakan fungsi std::next_permutation, kami boleh menjana dengan cekap semua kombinasi panjang r daripada set yang diberi.

Atas ialah kandungan terperinci Bagaimanakah C \'s `std::next_permutation` Boleh Digunakan untuk Menjana Semua Gabungan Saiz Tertentu?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!