enumerointia

Enumerointia tarkoittaa systemaattista kaikkien alkioiden tai kaikkien ratkaisujen listaamista jostakin joukosta. Sen tavoitteena on tuottaa konkreettinen luettelo sen sijaan, että vain määritettäisiin määrä. Enumerointi on keskeinen käsite sekä matematiikassa että tietojenkäsittelytieteessä, kun halutaan ymmärtää rakenteita tai löytää kaikki ratkaisut tietyllä ehdolla.

Matematiikassa enumerointi liittyy yhdistelmien, permutaatioiden ja osajoukkojen luettelointiin. Esimerkiksi voidaan listata kaikki n-joukon osajoukot tai kaikki permutaatiot. Tietojenkäyttöyssä samanlainen lähestymistapa tukee simulointia, testiaineistojen generaatiota sekä ongelmien täydellistä etsintää.

Algoritmeissa enumeration toteutetaan usein rekursion ja backtrackingin avulla, jolloin voidaan välttää turhia haaroja ja tuottaa ratkaisut yksi kerrallaan. Tavanomaisia järjestyksiä ovat lexikografinen järjestys sekä muut kokonaislukujärjestykset, joita käytetään generaattoreissa. Suuria kokonaisuuksia varten voidaan käyttää optimoituja generaattoreita, jotka tuottavat uuden alkion vain tarpeen mukaan (streaming tai lazy evaluation).

Esimerkki: osajoukkojen luettelo joukosta {a, b, c} antaa ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}. Enumerointi voi kasvaa eksponentiaalisesti – n joukon osajoukkojen määrä on 2^n – ja suurissa tapauksissa laskenta-aika voi olla ratkaiseva tekijä. Enumerointi on keskeinen osa algoritmien suunnittelua, optimointia ja tutkimusta.