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

Bagaimana untuk Menjana Semua k Gabungan n Item dalam C?

DDD
Lepaskan: 2024-11-21 07:56:11
asal
256 orang telah melayarinya

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

Algoritma untuk Menjana Kesemua k Gabungan n Item dalam C

Tugas di tangan adalah untuk mencipta program yang menjana dan memaparkan semua yang mungkin gabungan k orang yang berbeza daripada satu set n individu. Ini boleh dicapai menggunakan algoritma penjanaan gabungan, yang beroperasi seperti berikut:

Algoritma:

  1. Mulakan bitmask dengan urutan K mendahului 1: Bitmask ini menandakan bahawa orang K pertama dalam set pada mulanya diberikan kepada gabungan.
  2. Ubah saiz bitmask kepada N bit, menambahkan N-K mengekor 0s: Langkah ini memanjangkan bitmask untuk meliputi semua n orang dalam set.
  3. Lelaran melalui semua pilih atur yang mungkin bagi bitmask: Setiap pilih atur mewakili gabungan K orang yang berbeza.
  4. Untuk setiap pilih atur:

    • Ekstrak indeks bit set dalam bitmask. Indeks ini mewakili ahli gabungan semasa.
    • Cetak gabungan.
  5. Ulang langkah 3 sehingga semua pilih atur telah habis: Ini akan menghasilkan semua kemungkinan gabungan orang K daripada set n.

Pelaksanaan dalam C :

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

#include <algorithm>

#include <iostream>

#include <string>

 

void comb(int N, int K)

{

    std::string bitmask(K, 1); // K leading 1's

    bitmask.resize(N, 0); // N-K trailing 0's

 

    // print integers and permute bitmask

    do {

        for (int i = 0; i < N; ++i) // [0..N-1] integers

        {

            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

Sampel Output:

1

2

3

4

5

6

7

8

9

10

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

Atas ialah kandungan terperinci Bagaimana untuk Menjana Semua 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