Rumah > pembangunan bahagian belakang > C++ > Bagaimana Menjana Semua Kemungkinan k Gabungan n Item dalam C ?

Bagaimana Menjana Semua Kemungkinan k Gabungan n Item dalam C ?

DDD
Lepaskan: 2024-11-22 07:42:18
asal
745 orang telah melayarinya

How to Generate All Possible k Combinations of n Items in C  ?

Mencipta Semua Kemungkinan k Gabungan n Item dalam C

Memandangkan set integer dari 1 hingga n, tugasnya adalah untuk menjana dan cetak semua kemungkinan kombinasi k yang berbeza elemen.

Algoritma:

Masalah ini boleh diselesaikan menggunakan pendekatan berasaskan bitmask. Bitmask ialah perwakilan nombor di mana setiap bit menunjukkan kehadiran atau ketiadaan elemen dalam set.

Algoritma berfungsi seperti berikut:

  1. Janakan bitmask dengan petunjuk k 1s, mewakili k item pertama dalam gabungan.
  2. Ubah saiz topeng bit kepada n bit, dengan baki N-K bit ditetapkan kepada 0.
  3. Lelar melalui bitmask dengan panjang n, semak setiap bit.
  4. Untuk setiap bit yang ditetapkan kepada 1, cetak yang sepadan item.

Kod:

#include <algorithm>
#include <iostream>
#include <string>

void comb(int N, int K)
{
    std::string bitmask(K, 1);
    bitmask.resize(N, 0);

    do {
        for (int i = 0; i < N; ++i) {
            if (bitmask[i]) std::cout << " " << i;
        }
        std::cout << std::endl;
    } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
}

int main()
{
    comb(5, 3);
}
Salin selepas log masuk

Output:

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
Salin selepas log masuk

Analisis:

Algoritma ini menghasilkan kombinasi dengan memanipulasi bitmasks, iaitu cara yang cekap untuk mewakili set elemen. Kerumitan masa ialah O(n^k) untuk menjana semua gabungan yang mungkin.

Atas ialah kandungan terperinci Bagaimana Menjana Semua Kemungkinan k Gabungan n Item dalam C ?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan