Koodit: C: Järjestykset ja osajoukot

Tämä ohjelma muodostaa tietyn joukon järjestyksiä ja osajoukkoja.

Esimerkissä joukossa ovat kirjaimet A, B, C ja D, eli siinä on neljä alkiota.

Joukon järjestys tarkoittaa, kuinka monella tavalla joukosta voidaan valita tietty määrä alkioita.

Jos joukosta valitaan neljä alkiota, järjestykset ovat:
ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA

Jos joukosta valitaan kaksi alkiota, järjestykset ovat:
AB AC AD BA BC BD CA CB CD DA DB DC

Järjestysten määrän voi laskea kaavalla n! / (n - k)!, jossa n on alkioiden kokonaismäärä ja k on valittavien alkioiden määrä. Jos joukosta valitaan kaikki alkiot, kaava yksinkertaistuu muotoon n!. Valintaa voi ajatella näin: ensimmäisen alkion voi valita n tavalla, seuraavan n - 1 tavalla, seuraavan n - 2 tavalla jne. Viimeisen alkion voi valita aina vain yhdellä tavalla.

Kaavat pätevät esimerkkeihin: 4! = 24 ja 4! / (4 - 2)! = 24 / 2 = 12.

Joukon osajoukko tarkoittaa, kuinka monella tavalla joukosta voidaan valita osa alkioista.

Jos joukosta muodostetaan kaikki osajoukot, ne ovat:
ABCD ABC ABD AB ACD AC AD A BCD BC BD B CD C D

Jos joukosta muodostetaan kaksialkioiset osajoukot, ne ovat:
AB AC AD BC BD CD

Kaikkien osajoukkojen määrän voi laskea kaavalla 2 ^ n, jossa n on alkioiden kokonaismäärä. Muodostamista voi ajatella näin: jokaisen alkion voi joko ottaa osajoukkoon tai jättää pois, eli jokaisen alkion kohdalla on kaksi vaihtoehtoa. Tietynkokoisten osajoukkojen määrän voi laskea kaavalla n! / (k! * (n - k)!), jossa n on alkioiden kokonaismäärä ja k on kunkin osajoukon koko.

Kaavat pätevät esimerkkeihin: 2 ^ 4 = 16 ja 4! / (2! * (4 - 2)!) = 24 / (2 * 2) = 24 / 4 = 6.

Mutta miksi osajoukkoja näkyy listassa vain 15? Yksi osajoukoista on tyhjä, eli siinä ei ole yhtään alkiota!

Järjestyksen ja osajoukon ero on siinä, että osajoukossa alkioiden ilmoitusjärjestyksellä ei ole merkitystä. Esim. alkiot A, B ja C ovat vain yksi osajoukko, mutta niistä voidaan muodostaa kuusi erilaista järjestystä.

Ohjelman funktiot ovat jarj, joka muodostaa järjestykset (kaikista alkioista tai vain osasta), osaj, joka muodostaa kaikki osajoukot ja osajn, joka muodostaa tietynkokoiset osajoukot. Kaikki funktiot käyttävät hyväkseen rekursiota (eli ne kutsuvat itseään) ja perustuvat melko suoraan yllä mainittuihin ajattelutapoihin.

Järjestyksille ja osajoukoille on paljon sovelluksia ohjelmoinnissa, niin kuin olet ehkä huomannutkin!

#include <stdio.h>

char merkit[] = "ABCDEFGHIJKLMN";
char tulos[10];

int mukana[9] = {0};

/* tulostaa annetun pituisen kirjainjonon */
void tulosta(int pituus) {
    tulos[pituus] = '\0';
    printf("%s ", tulos);
}

/* muodostaa kirjainten järjestykset
     kohta  = 0
     raja   = kirjainten kokonaismäärä
     maara  = järjestyksen kirjainmäärä
*/
void jarj(int kohta, int raja, int maara) {
    int i;
    /* onko kirjainjono valmis? */
    if (kohta == maara) {
        tulosta(maara);
        return;
    }
    for (i = 0; i < raja; i++) {
        /* onko kirjainta vielä mukana? */
        if (!mukana[i]) {
            mukana[i] = 1;
            tulos[kohta] = merkit[i];
            jarj(kohta + 1, raja, maara);
            mukana[i] = 0;
        }
    }
}

/* muodostaa kirjainten kaikki osajoukot
     kohta  = 0
     raja   = kirjainten kokonaismäärä
     pituus = 0
*/
void osaj(int kohta, int raja, int pituus) {
    /* onko kirjainjono valmis? */
    if (kohta == raja) {
        tulosta(pituus);
        return;
    }
    tulos[pituus] = merkit[kohta];
    /* käsiteltävä kirjain otetaan mukaan */
    osaj(kohta + 1, raja, pituus + 1);
    /* käsiteltävää kirjainta ei oteta mukaan */
    osaj(kohta + 1, raja, pituus);
}

/* muodostaa kirjainten tietynkokoiset osajoukot
     kohta  = 0
     raja   = kirjainten kokonaismäärä
     pituus = 0
     maara  = osajoukon kirjainmäärä
*/
void osajn(int kohta, int raja, int pituus, int maara) {
    /* onko jäljellä riittävästi kirjaimia? */
    if (raja - kohta < maara - pituus) {
        return;
    }
    /* onko kirjainjono valmis? */
    if (pituus == maara) {
        tulosta(pituus);
        return;
    }
    tulos[pituus] = merkit[kohta];
    /* käsiteltävä kirjain otetaan mukaan */
    osajn(kohta + 1, raja, pituus + 1, maara);
    /* käsiteltävää kirjainta ei oteta mukaan */
    osajn(kohta + 1, raja, pituus, maara);
}

int main(void) {
    printf("4 kirjainta, 4 kirjaimen järjestykset:\n");
    jarj(0, 4, 4);
    printf("\n\n4 kirjainta, 2 kirjaimen järjestykset:\n");
    jarj(0, 4, 2);
    printf("\n\n4 kirjainta, kaikki osajoukot:\n");
    osaj(0, 4, 0);
    printf("\n\n4 kirjainta, 2 kirjaimen osajoukot:\n");
    osajn(0, 4, 0, 2);
    return 0;
}