algorytm znajdywania wszystkich podzbiorów danego zbioru

Witam!

Interesuje mnie algorytm znajdywania wszystkich podzbiorów danego zbioru. Czyli na wejściu mam ilość elementów w danym zbiorze, a na wyjściu liste wszystkich podzbiorów zbioru {1,2,...,n}. Przykładowo dla wejścia n=3, program powinien wypluć listę {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.

Mój pomysł jest taki, żeby podzbiory utożsamić z liczbami binarnymi o n-bitach (0 na k-tym bicie oznacza, że k należy do danego podzbioru, 1, że do niego nie należy), jednak może można inaczej, szybciej, lepiej.

Wszelkie sugestie będą dla mnie bardzo cenne. Z góry dziękuję za pomoc, pozdrawiam!

Nie bardzo rozumiem jak chcesz wykorzystać to utożsamienie z liczbami binarnymi. Nie możesz po prostu puścić rekurencji?

@Shalom - chyba zartujesz :> Wersja iteracyjna przynajmniej nie przeladuje stosu ;p

edit: poszukaj na forum, bylo juz pare razy.

Można to zrobić rekurencyjnie np. tak:

int main()
{
    int n;
    cin>>n;
    List l;
    for(int i=0;i<=n;i++)
        podzbiory(l,i,n,1);
    return 0;
}

void podzbiory(List l,int n,int k, int m) //l - stos na którym mamy aktualne elementy podzbioru, n-ile jeszcze mamy dołożyć, k- maksymalna wartość elementu który możemy dołozyć, m- minimalna wartość
{
    if(n==0)
        l.show(); //wypisanie całej zawartości stosu
    else
        for(int i=m;i<=k;i++)
        {
            l.push(i);
            podzbiory(l,n-1,k,i+1);
            l.pop();
        }
}

Shalom napisał(a)

Nie bardzo rozumiem jak chcesz wykorzystać to utożsamienie z liczbami binarnymi. Nie możesz po prostu puścić rekurencji?

dość prosto, wyjaśnię na przykladzie. Mam na wejściu n=2, więc będę chcial miec na wyjsciu listę {{},{1},{2},{1,2}}, biorę więc wszystkie liczby 00, 01, 10 i 11 (bity to należenie odpowiedniego elementu do zbioru bądź nie, czyli 00={}, 01={1}, 10={2}, 11={1,2}), jasne już?

sam sobie odpowiedziałeś:

#include <stdio.h>

int main(int argc, char **argv)
{
    //jak potrzebujesz wiecej elementow, zmien typ na unsigned long long int
    #define TYP unsigned int
    
    #define TYP_ILE unsigned char
    
    TYP zbior_pelny ; //zmienna reprezentujaca zbior pelny 
    TYP_ILE ilosc_elementow ; //ile elementow moze zawierac ten zbior
    
    //iteratory
    TYP i ;
    TYP_ILE j ;
    
    //wypelnienie jedynkami:
    zbior_pelny = 0xFFFFFFFF ;
    //zbior pelny = 11111111111111111111111111111111 ;
    
    printf("ilosc elementow = ") ;
    scanf("%u",&ilosc_elementow) ;
    
    //zalozmy, ze podalismy 5
    
    //usuniecie niepotrzebnych jedynek
    if (ilosc_elementow==0)
        zbior_pelny=0 ;
    else        
        zbior_pelny>>=(32-ilosc_elementow) ;
    //zbior pelny = 00000000000000000000000000011111 ; - jak widac, zbior pelny 5 elementow
    
    //iteracja od zbioru pustego do pelnego uwzgledniajace wszystkie wariacje z powtorzeniami
    for (i=0; i<=zbior_pelny; ++i)
        //teraz trzeba wypisac te elementy
        {
            printf("Podzbior nr. %u zawiera elementy: {",(i+1)) ;
            for (j=0; j<ilosc_elementow; ++j)
                //sprawdzanie kazdego bitu - czyli obecnosci kazdego elementu w zbiorze
                if (i&(1<<j))
                {                    
                    printf("element_%u",(j+1)) ;
                    if (j!=ilosc_elementow-1)
                        printf(", ") ;
                }
            printf("}\n") ;
        }
        
    return 0;
}

ilosc elementow = 5
Podzbior nr. 1 zawiera elementy: {}
Podzbior nr. 2 zawiera elementy: {element_1, }
Podzbior nr. 3 zawiera elementy: {element_2, }
Podzbior nr. 4 zawiera elementy: {element_1, element_2, }
Podzbior nr. 5 zawiera elementy: {element_3, }
Podzbior nr. 6 zawiera elementy: {element_1, element_3, }
Podzbior nr. 7 zawiera elementy: {element_2, element_3, }
Podzbior nr. 8 zawiera elementy: {element_1, element_2, element_3, }
Podzbior nr. 9 zawiera elementy: {element_4, }
Podzbior nr. 10 zawiera elementy: {element_1, element_4, }
Podzbior nr. 11 zawiera elementy: {element_2, element_4, }
Podzbior nr. 12 zawiera elementy: {element_1, element_2, element_4, }
Podzbior nr. 13 zawiera elementy: {element_3, element_4, }
Podzbior nr. 14 zawiera elementy: {element_1, element_3, element_4, }
Podzbior nr. 15 zawiera elementy: {element_2, element_3, element_4, }
Podzbior nr. 16 zawiera elementy: {element_1, element_2, element_3, element_4, }
Podzbior nr. 17 zawiera elementy: {element_5}
Podzbior nr. 18 zawiera elementy: {element_1, element_5}
Podzbior nr. 19 zawiera elementy: {element_2, element_5}
Podzbior nr. 20 zawiera elementy: {element_1, element_2, element_5}
Podzbior nr. 21 zawiera elementy: {element_3, element_5}
Podzbior nr. 22 zawiera elementy: {element_1, element_3, element_5}
Podzbior nr. 23 zawiera elementy: {element_2, element_3, element_5}
Podzbior nr. 24 zawiera elementy: {element_1, element_2, element_3, element_5}
Podzbior nr. 25 zawiera elementy: {element_4, element_5}
Podzbior nr. 26 zawiera elementy: {element_1, element_4, element_5}
Podzbior nr. 27 zawiera elementy: {element_2, element_4, element_5}
Podzbior nr. 28 zawiera elementy: {element_1, element_2, element_4, element_5}
Podzbior nr. 29 zawiera elementy: {element_3, element_4, element_5}
Podzbior nr. 30 zawiera elementy: {element_1, element_3, element_4, element_5}
Podzbior nr. 31 zawiera elementy: {element_2, element_3, element_4, element_5}
Podzbior nr. 32 zawiera elementy: {element_1, element_2, element_3, element_4, element_5}