Kihagyás

Halmaz

Halmaz típus

A programozásban számtalan formában előfordulhatnak halmazok és halmazokkal végzett műveletek. A lényege ennek a típusnak, hogy adott egy univerzum (U), ami tartalmazza a potenciális elemeit a halmaznak (ezeket legtöbbször egész számokkal ábrázoljuk, hisz a lényeg, hogy diszkrét, egymástól jól elkülöníthető elemeket kell definiálnunk). A P(U)értékhalmaz visszaadja az U univerzum összes lehetséges részhalmazainak halmazát. Ez lesz a Halmaz(U) új adattípus értékhalmaza. Azaz egy halmaz pillanatnyi állapotát az határozza meg, hogy az univerzum elemei az adott halmazba beletartoznak-e, vagy sem.

Halmaz, mint absztrakt adattípus

Mivel a halmaznak konkrét megvalósítása nincs C nyelven, így még egyértelműbb az az igény, hogy a halmaz műveleteit absztrakt módon adjuk meg. Azt, hogy ezt utána hogyan valósítjuk meg, mindig az adott probléma fogja meghatározni.

A halmaz adattípustól elvárt műveleteket a következő táblázat foglalja össze:

Művelet megnevezése Művelet leírása
Üresít(\(\leftarrow\) H:Halmaz); A H halmaz elemeit törli. Eredmény egy üres halmaz.
Bővít(\(\leftrightarrow\) H:Halmaz; \(\rightarrow\) x:U); A művelet a H változó értékéhez hozzáveszi az x elemet.
Töröl(\(\leftrightarrow\) H:Halmaz; \(\rightarrow\) x:U); A művelet a H változó értékéből törli az x elemet.
Eleme(\(\rightarrow\) x:U; \(\rightarrow\) H:Halmaz):bool; A függvényművelet akkor és csak akkor ad igaz értéket, ha x\(\in\) H halmaznak.
Egyesítés(\(\rightarrow\) H1:Halmaz; \(\rightarrow\) H2:Halmaz; \(\leftarrow\) H:Halmaz); A művelet eredményeként a H változó értéke a H1 \(\cup\) H2 lesz.
Metszet(\(\rightarrow\) H1:Halmaz; \(\rightarrow\); H2:Halmaz; \(\leftarrow\) H:Halmaz); A művelet eredményeként a H változó értéke a H1 \(\cap\) H2 lesz.
Különbség(\(\rightarrow\)H1:Halmaz; \(\rightarrow\) H2:Halmaz; \(\leftarrow\) H:Halmaz); A művelet eredményeként a \(H\) változó azokat az x \(\in\) H1 elemeket tartalmazza, melyekre x \(\not\in\) H2.
Egyenlő(\(\rightarrow\) H1:Halmaz; \(\rightarrow\) H2:Halmaz):bool; Az egyenlőség relációs művelet.
Rész(\(\rightarrow\) H1:Halmaz; \(\rightarrow\) H2:Halmaz):bool; Akkor és csak akkor ad igaz értéket, ha a H1 \(\subseteq\) H2.
Ürese(\(\rightarrow\) H:Halmaz):bool; Akkor és csak akkor ad igaz értéket, ha H=\(\emptyset\).
Értékadás(\(\leftarrow\) H1:Halmaz; \(\rightarrow\) H2:Halmaz); A művelet hatására a H1 változó felveszi a H2 értékét.

Halmaz, mint virtuális adattípus

Ahogy az már szóba került, nincs a halmaznak konkrét megvalósítása C nyelven. Ellenben számos módszerrel meg tudjuk azt valósítani mégis. Mi kell ehhez? A halmazok reprezentálásánál a kulcsszerep annak a kérdésnek jut, ami megválaszolja az univerzum összes elemére, hogy adott elem része-e az adott halmaznak, vagy sem. Az H U-beli részhalmaz megadható annak karakterisztikus függvényével, ami minden U-beli elemhez 0-át, vagy 1-et rendel, attól függően, hogy az adott elem eleme e a halmaznak, vagy sem:

\(k_H: U\to\{0,1\}\)

\(k_H(x) = \left\{ \begin{array}{ll} 1 & \Leftrightarrow x\in H\\ 0 & \Leftrightarrow x\not\in H\\ \end{array}\right.\)

Egy kézenfekvő megoldás a halmazok megadására, hogy egy univerzum méretének megfelelő bool tömbben tároljuk el minden elemre, hogy az eleme, vagy nem az adott halmaznak. Bár ez megoldás lehet, azonban nagyobb halmazok esetében nem gazdaságos megoldás, hiszen egy bool érték eltárolásához legalább egy (de az is lehet, hogy négy) bájt kell, holott az egész információ tartalom 1 biten is elfér.

Ehelyett próbáljuk azt, hogy valamely egész típust felhasználva egyetlen egész típusú változóban tároljuk el több halmazelem karakterisztikus értékét. Például ha adott egy 32 bites int változónk, akkor az alkalmas egy 32 elemű kisebb halmaz reprezentálására, ahol minden egyes bitnek meg van feleltetve az univerzum egy eleme. Például:

kep

vagy

kep

Nyilván a könnyebb kezelhetőség érdekében érdemes a bitek sorrendjében valami rendezettséget találni.

Az egyes biteket ezután a bitműveletek segítségével könnyen el tudjuk érni:

kep

Illetve a további bitműveletekkel, mint a &, | és ~ segíthetik a bitek beállítását, törlését, lekérdezését.

Ha nagyobb halmazokat szeretnénk létrehozni, akkor azt összepakolhatjuk kishalmazokból. Az elemeket sorszámozva az egész osztás segít abban, hogy megtaláljuk, adott elemhez rendelt karakterisztikus értéket melyik kishalmazban találjuk. Ehhez az elem sorszámát kell osztani a kishalmaz méretével (azaz egy kishalmazban tárolható elemek számával). Kishalmazon belül pedig a pozíciót hasonló, csak épp maradékos osztással kapjuk meg:

kep

Könnyen belátható, hogy ezzel a módszerrel minden \(x\) természetes szám egyértelműen meghatározható az \((x/K, x%K)\) számpárral. Egy \(x\) akkor és csak akkor eleme a \(H\) változó által reprezentált halmaznak, ha teljesül, hogy a \(H[x/K]\) kishalmaznak eleme az \((x%K)\), azaz a megfelelő kishalmaz megfelelő bitje 1.
Az univerzum méretét egyértelműen meghatározza a kishalmazt ábrázoló adattípus mérete, illetve az, hogy ilyen kishalmazból mennyit használunk fel.

Mivel a halmazt tényleg megvalósíthatjuk többféleképpen is, érdemes ezt úgy megtenni, hogy igény szerint adott megvalósítás könnyen lecserélhető legyen. Ebben segít nekünk a moduláris programozás lehetősége, illetve az, hogy magát az absztrakt típust leíró függvény deklarációkat a definícióktól külön tudjuk megadni, és használni.

Hozzunk létre egy külön header állományt (legyen a neve most ennek halmaz_t.h), amiben az alábbiakat írjuk:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#ifndef HALMAZ_H
#define HALMAZ_H

#include <stdbool.h>

#define K (8*sizeof(KisHalmaz))
#define M ???
#define H_MAX (M*K)

typedef unsigned long int halmazelem;
typedef halmazelem KisHalmaz;
typedef KisHalmaz Halmaz[M];

void Uresit(Halmaz);
void Bovit(Halmaz, halmazelem);
void Torol(Halmaz, halmazelem);
bool Eleme(Halmaz, halmazelem);
void Egyesites(Halmaz H1, Halmaz H2, Halmaz H);
void Metszet(Halmaz H1, Halmaz H2, Halmaz H);
void Kulonbseg(Halmaz H1, Halmaz H2, Halmaz H);
bool Egyenlo(Halmaz H1, Halmaz H2);
bool Resz(Halmaz H1, Halmaz H2);
bool Urese(Halmaz H);
void Ertekadas(Halmaz H1, Halmaz H2);

#endif // HALMAZ_H

Az M méretet természetesen úgy definiáljuk, ahogy az az adott feladatunk számára szükséges.

Mielőtt tovább haladnánk, nézzük meg alaposabban is a fenti kódot! Az egész kód egy pár makró által keretbe lett foglalva. Minden header esetében vigyázni kell arra, hogy az include-olások által a benne szereplő deklarációk ne duplikálódjanak, mert ebben az esetben a kód nem fordulna le. Egy egyszerű trükkel akadályozza meg minden header állomány a kód többszörös bekerülését a fordításba. Amikor a fordító találkozik a header állomány kódjával, a header nevéből képzett makró létezésének ellenőrzésével vizsgálja, hogy a header már bekerült-e a fordításba. Amennyiben a makró még nem definiált (#ifndef HALMAZ_H) (azaz a fordító először látja a kódot), akkor a makró definiálásra kerül (#define HALMAZ_H). A következő kódokat a fordító figyelembe veszi.

Amikor újra ezen állomány vizsgálatához érkezne a fordító (pl. többszörös include-ok miatt), a makró ellenőrzése jelzi, hogy itt már járt, azok a kódok, amik az #endif utasításig vannak, nem kerülnek be újra a fordításba.

Ha definiálunk emellett egy halmaz_t.c állományt, abban megadhatjuk az egyes függvények implementációját is: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include "halmaz_t.h"

void Uresit(Halmaz H) {
    long int i;
    for(i = 0; i < M; ++i)
        H[i] = 0;
}

void Bovit(Halmaz H, halmazelem x) {
    if(x < H_MAX)
        H[x / K] |=  (1l << (x % K));
}

void Torol(Halmaz H, halmazelem x) {
    if(x < H_MAX)
        H[x / K] &= ~(1l << (x % K));
}

bool Eleme(halmazelem x, Halmaz H) {
    return (x < H_MAX) && (H[x / K] & (1l << (x % K)));
}

void Egyesites(Halmaz H1, Halmaz H2, Halmaz H) {
    long int i;
    for(i = 0; i < M; ++i)
        H[i] = H1[i] | H2[i];
}

void Metszet(Halmaz H1, Halmaz H2, Halmaz H) {
    long int i;
    for(i = 0; i < M; ++i)
        H[i] = H1[i] & H2[i];
}

void Kulonbseg(Halmaz H1, Halmaz H2, Halmaz H) {
    long int i;
    for(i = 0; i < M; ++i)
        H[i] = H1[i] & ~(H2[i]);
}

bool Egyenlo(Halmaz H1, Halmaz H2) {
    long int i;
    for(i = 0; (i < M) && (H1[i] == H2[i]); ++i);
    return i == M;
}

\begin{lstlisting}[firstnumber=47]
bool Resz(Halmaz H1, Halmaz H2) {
    long int i;
    for(i = 0; (i<M) && !(H1[i] & ~(H2[i])); ++i);
    return i == M;
}

bool Urese(Halmaz H) {
    long int i;
    for(i = 0; (i < M) && !(H[i]); ++i);
    return i == M;
}

void Ertekadas(Halmaz H1, Halmaz H2) {
    long int i;
    for(i = 0; i < M; ++i)
        H1[i] = H2[i];
}

Természetesen ha másfajta megvalósítást használnánk, akkor elég csak ezt a c állományt más implementációra cserélni, a headerben kiemelt résznek köszönhetően nem kell a felhasználó kódok implementációját változtatni.

Diszkrét ismétléses vezérlés és a halmazok

Emlékezzünk vissza, hogy a vezérlési módok megismerése során a diszkrét ismétlésnél is kiemeltük, hogy annak nincs C-beli megvalósítása. Azután viszont, hogy az univerzumot reprezentálni tudjuk, lehetőség nyílik arra, hogy a diszkrét ismétléses vezérlést megfogalmazzuk ezekre az esetekre.

Ha megtudjuk adni az univerzum legkisebb és legnagyobb elemeit, az elemeken pedig végig tudunk lépdelni egy megadott rendezés által, akkor a diszkrét ismétléses vezérlés megvalósítható az alábbi módon:

kep

aminek C-beli megvalósítása:

1
2
3
4
5
for(x = U_min; x <= U_max; ++x) {
    if(Eleme(x,H)) {
        M;
    }
}

Példa: klikk meghatározása

  • Problémafelvetés:
    • Egy közösségben az emberek közötti barátsági kapcsolat alapján meg kell határoznunk a klikkeket!
  • Specifikáció:
    • Legyen egy előre adott \(N\) az emberek száma, akiket jelöljünk az \(1, \dots, N\) számokkal.
    • A program inputja \((i, j)\) számpárok sorozata (\(1\leq i, j\leq N\)), ami az \(i.\) és \(j.\) sorszámú ember barátságát jelenti. A sorozat (és az input) végét a \((0, 0)\) számpár jelenti.
    • Az output a baráti csoportok tagjainak felsorolása.
  • Algoritmustervezés - a matematika nyelvén:
    • Tegyük fel, hogy a barátság reflexív, szimmetrikus és tranzitív reláció. Meg kell határozni az \(R\) relációt tartalmazó legszűkebb ekvivalencia reláció szerinti osztályozást!
    • Induljunk ki abból, hogy minden személy csak saját magával van barátságban (reflexív); tehát képezzük az \({i}\) egy elemű halmazokat!
    • Ha az input számpárokat valameddig feldolgozva meghatároztuk az osztályozást, a következő \((i,j)\) számpárt beolvasva össze kell vonni azt a két részhalmazt, amelybe \(i\) illetve \(j\) tartozik, hisz mindenki, aki \(i\)-vel barátságban van, az barátságban van \(j\) minden barátjával is (tranzitív), és ez fordítva is igaz (szimmetrikus).

első megközelítésben kódoljuk le a fenti megoldást úgy, hogy a megfelelő műveleteket csak az absztrakt művelet megnevezésével adjuk meg. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/* A beolvasott R relációt tartalmazó legszűkebb ekvivalencia
   reláció szerinti osztályozást határozzuk meg.
   Vázlat, nem fordítható C program.
   2006. Augusztus 14. Gergely Tamás, gertom@inf.u-szeged.hu
 */
#include <stdio.h>
#define N 10                                            /* maximális elemszám */
typedef Halmaz(U) Halmaz;                                  /* EZ ÍGY NEM C !!!*/

int main() {
    Halmaz H[N];
    unsigned short i,j, ti,tj;
    for(i = 1; i <= N; ++i) {                                /* inicializálás */
        Uresit(H[i-1]); Bovit(H[i-1], i);
    }
    printf("Kérem a relációban lévő számpárokat!\n");
    scanf("%hd%hd%*[^\n]", &i, &j);
    getchar();
    while(i != 0) {
        for(ti=0; !Eleme(i, H[ti]); ti++); /* amelyik H[ti] halmazban van i ? */
        for(tj=0; !Eleme(j, H[tj]); tj++); /* amelyik H[tj] halmazban van j ? */
        if(ti != tj) {                          /* H[ti] és H[tj] összevonása */
            Egyesites(H[ti], H[tj], H[ti]);
            Uresit( H[tj] );
        }
        scanf("%hd%hd%*[^\n]", &i, &j);
        getchar();
    }
    printf("Az osztályok: \n");
    for (i = 1; i <= N; i++) {                      /* az osztályok kiíratása */
        if (! Urese(H[i - 1])) {
            for (j = 1; j <= N; j++) {
                if (Eleme(j, H[i - 1]))
                    printf("%4hd,", j);
            }
            putchar('\n');
        }
    }
}

Nyilván ez a kód nem lesz fordítható, de gyorsan és könnyen megadja a programunk vázát, amit utána csak annyival kell módosítani, hogy amikor eldőlt, milyen halmaz reprezentációt alkalmazunk, akkor ezeket a műveleteket annak megfelelően valósítjuk meg. Jelen esetben elég egy kishalmaz a halmazunk reprezentálására, így ennek megfelelően átírhatjuk a kódban a műveleteket:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/* A beolvasott R relációt tartalmazó legszűkebb ekvivalencia
 *   reláció szerinti osztályozást határozzuk meg.
 * 1997. December 6.  Dévényi Károly, devenyi@inf.u-szeged.hu
 */

#include <stdio.h>

#define N  10                                       /* maximális elemszám */

typedef unsigned short int univerzum_t;                   /* az univerzum */
typedef long int halmaz_t;        /* N kicsi, ezért elegendő egy long int */

int main(int argc, char *argv[]) {
    halmaz_t h[N];
    univerzum_t i, j, ti, tj;

    for (i = 1; i <= N; ++i) {                           /* inicializálás */
        h[i - 1] = 1l << i;
    }

    printf("Kérem a relációban lévö számpárokat!\n");
    scanf("%hd%hd%*[^\n]", &i, &j); getchar();
    while (i != 0) {
                        /* az i-t tartalmazó halmaz ti indexének keresése */
        for (ti = 0; ((1l << i) & h[ti]) == 0; ++ti);
                         /* a j-t tartalmazó halmaz tj indexének keresése */
        for (tj = 0; ((1l << j) & h[tj]) == 0; ++tj);
        if (ti != tj) {                     /* h[ti] és h[tj] összevonása */
            h[ti] |= h[tj];
            h[tj] = 0;
        }
        scanf("%hd%hd%*[^\n]", &i, &j); getchar();
    }

    printf("Az osztályok:\n");
    for (i = 1; i <= N; ++i) {                  /* az osztályok kiíratása */
        if (h[i - 1] != 0) {
            for (j = 1; j <= N; ++j) {
                if (((1l << j) & h[i - 1]) != 0)
                    printf("%4d,", j);
            }
            putchar('\n');
        }
    }
    return 0;
}

Példa: prímszámok meghatározása

  • Problémafelvetés:
    • Határozzuk meg az adott \(N\) természetes számnál nem nagyobb prímszámokat.
  • Specifikáció:
    • Legyen \(N\) egy előre adott pozitív egész szám.
    • A programnak nincs bemenete.
    • A kimenet a \([0, N)\) intervallumba eső prímszámok sorozata.
  • Algoritmustervezés:
    • Egyesével minden számról \(N\)-ig döntsük el, hogy prím-e, vagy sem.
    • Az előbbi elképzelés nyilván nem a legoptimálisabb, már ami a futási idejét illeti a programnak.
    • Éppen ezért használjuk a prímszámok meghatározására a jól ismert Erathosztenészi szita algoritmust:
      • A halmazt kezdetben feltöltjük az egynél nagyobb páratlan számokkal.
      • Megkeressük a halmaz még nem feldolgozott legkisebb elemét (ez prímszám lesz) és töröljük a többszöröseit.
      • Az előző pontot addig ismételjük, míg el nem érjük az \(N\) gyökét. (Ezután következő nem prím számok már biztosan ki vannak rostálva.)
      • Az eredményhalmaz csak a prímszámokat fogja tartalmazni.
  • Algoritmustervezés szerkezeti ábrával:

kep

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/* Határozzuk meg az adott N természetes számnál nem nagyobb
 *   prímszámokat.
 * 1997. December 6.  Dévényi Károly, devenyi@inf.u-szeged.hu
 * 2006. Augusztus 15.  Gergely Tamás, gertom@inf.u-szeged.hu
 */

#include <stdio.h>

#define K (8 * sizeof(kishalmaz_t))
#define M 262144LL
#define N (M * K)

typedef long long int kishalmaz_t;
typedef kishalmaz_t halmaz_t[M];

int main() {
    halmaz_t szita;
    kishalmaz_t kicsi;                         /* a szita inicializálásához */
    long long int p, s, lepes, i, j;

    kicsi = 0;                                  /* a szita inicializálása */
    for (i = 0; i <= ((K - 1) / 2); ++i) {
        kicsi |= (1LL << (2 * i + 1));
    }
    for (i = 0; i < M; ++i) {
        szita[i] = kicsi;
    }
    szita[0] &= ~2LL; /* 2LL == (1LL << 1) */
    szita[0] |= 4LL;  /* 4LL == (1LL << 2) */

    p = 3;                                     /* az első szitálandó prím */
    while (p * p  < N) {                 /* P többszöröseinek kiszitálása */
        lepes = 2 * p;                                  /* lépésköz = 2*p */
        s = p * p;                                /* s az első többszörös */
        while (s < N) {
            szita[s / K] &= ~(1LL << (s % K));
            s += lepes;
        }
        do {                                 /* a következő prím keresése */
            p += 2;
        } while ((p < N) && !(szita[p / K] & (1LL << (p % K))));
    }

    j = 0;                           /* a prímszámok kiíratása képernyőre */
    printf("A prímszámok %lld-ig:\n", N);
    for (p = 2; p < N; ++p) {
        if (szita[p / K] & (1LL << (p % K))) {
            printf("%9lld", p);
            if (++j == 8) {
                j = 0;
                putchar('\n');
            }
        }
    }
    putchar('\n');
    return 0;
}

Mivel \(N\) elég nagy lehet, így most a halmazok ábrázolására nem elég egyetlen egész típusú változó, azok összerakásával kell meghatároznunk az univerzumot. A kishalmazunk típusának az implementációban long long int-et használtunk. Figyeljük meg ehhez kapcsolódóan, hogy mivel a célunk ezzel az, hogy ebben tárolt adatokkal mindenféle bitművelet segítségével megvalósítani a halmaz műveleteit, és ehhez az kell, hogy konstans adatokkal is ügyeskedjünk mellette, így nagyon fontos, hogy a konstansok megadásánál is az LL utótaggal jelezzük a konstans típusát.

Első pillanatra talán a megannyi bitművelet elrettentő lehet, így nézzük meg őket alaposabban:

  • kicsi halmaz inicializálása:
    • a 21. sorban kicsi változó minden bitje 0 lesz
    • 22-23.sor: minden páratlan pozíciójú bitet (azaz a páratlan számokat reprezentáló biteket) 1-re állítjuk, azaz a páros bitek 0-ák maradnak.
    • 25-27. sor: minden kishalmazt inicializálunk ezzel az ...10101 bitsorozattal.
    • 28-29. sor: mivel az 1 nem prím, így azt ki kell venni a halmazból, a 2 viszont az, azt be kell tenni.
  • szitálás:
      1. sor : nem kell a ciklisnak \(N\)-ig mennie, hiszen ha elérjük azt az állapotot, hogy az első még nem vizsgált prím négyzete nagyobb \(N\)-nél, akkor tudjuk, hogy a prím önmagánál kisebb többszörösei már ki vannak rostálva.
      1. sor: a többszörösök meghatározására állítjuk be a lepes változót. Mivel minden páros többszörös már ki van rostálva, így ez a lépésköz lehet a prím 2-szerese, a páros értékeket felesleges újra kiszórni.
      1. sor: az első kiszórandó érték meghatározása. Mivel az aktuális prímnél kisebb többszörösei már ki vannak szórva az aktuális prímnek, így ez az érték az aktuális prím négyzete.
    • 39-40. sor: következő, még prím keresése (azaz az első olyan szám keresése, ami az aktuális prím után benne van a szitában)
Utolsó frissítés: 2022-11-25 15:25:14