Black Wolf - osobní stránky

Potenční množina v C++

Aby toho nebylo málo, dovolím si ještě jednu „školní” programátorskou úlohu – generování potenční množiny. Nabízí se dvě možná řešení – rekurzivní a iterativní. U prvního však pouze popíši postup, neboť jsem problém řešil způsobem druhým.

Myšlenka rekurzivního řešení je velmi prostá – potenční množina n-prvkové množiny je složena ze všech jejích 0 až n-prvkových podmnožin. Vygenerování 0-prvkové je triviální a m-prvkovou (pro m>0 a m<=n) získáme tak, že vytvoříme všechny jednoprvkové podmnožiny a pro každou z nich uděláme její sjednocení se všemi m-1 prvkovými podmnožinami které tento prvek ještě neobsahují (ty získáme rekurzivní aplikací tohoto postupu).

Iterativní řešení je myšlenkově kapánek složitější, ale kódově jednodušší a mělo by být i výkonnější (nedochází k rekurzivnímu volání funkcí a s jednou alokovanou pamětí se už dále nehýbe). Místo vstupní množiny si představíme stejně velkou množinu kde na každém místě může být buď jednička nebo nula a vygenerujeme všechny možné kombinace jedniček a nul – tzn. bude se jednat o variace n-té třídy ze 2 prvků. Podle každé z těchto variací vygenerujeme jednu množinu potenční množiny a to tak, že do výsledné množiny zařadíme k-tý prvek vstupní množiny právě když na k-tém místě aktuálně uvažované variace je jednička.

A aby to bylo celé ještě jednodušší, pro vygenerování zmíněných variací stačí vzít binární reprezentaci čísel 0 až 2ⁿ (počet variací n-prvkové množiny je právě 2ⁿ a číslo reprezentované binárním zápisem sestávajícím z n jedniček je taktéž 2ⁿ).

Teorie by snad stačila, takže teď praktická implementace. Pro reprezentaci množiny je použita jednoduchá struktura a díky využití templatů je možno pracovat s libovolným datovým typem což má také tu výhodu, že potenční množina je stejného datového typu jako jakákoli jiná množina.

template <class T> struct set_t{
    int size;
    T* set;
};

template <class T> set_t<set_t<T>*>* potencni(set_t<T>* vstup){
    set_t<set_t<T>*>* ret = new set_t<set_t<T>*>;
    T pom[vstup->size];
    int count=0,i,j,k;

    ret->size = (int)pow(2,vstup->size);
    ret->set = new set_t<T>*[ret->size];

    for(i=0;i<ret->size;++i,count=0){
        for(j=1,k=1;j<=vstup->size;++j,k*=2){
            if((i&k) == k){
               pom[count++] = vstup->set[j-1];
            }
        }
        (ret->set)[i] = new set_t<T>;
        ((ret->set)[i])->size = count;
        ((ret->set)[i])->set = new T[count];
        memcpy(((ret->set)[i])->set,pom,sizeof(T)*count);
    }

    return ret;
}

Publikováno 05.01.2008 18:27 v sekci IT
Trvalý odkaz
Komentářů: 0 (Zobrazit komentáře)