Powerset

julieann

Hey!

Ich brauche mal wieder Hilfe, nachdem ich das letzte Projekt einigermaßen auf die Reihe gekriegt habe.

Ich muss eine Funktion implementieren, mit der alle l-elementigen Teilmengen einer Menge N ( N = {1,...,n} ist die zugehörige Indexmenge) erzeugt werden können. Als Eingabeparameter benötigt die Funktion natürlich n und l. Insbesondere sollen auf keinen Fall alle Teilmengen gleichzeitig
erzeugt (und z. B. in einer Matrix oder Liste zurückgegeben) werden.

Es handelt sich dabei ja um ein Powerset, oder? Nur, dass ich nicht alle Teilmengen brauche.
Ich habe ein Skript für Powerset bei char Arrays. Aber ich kriege es nicht vernünftig abgewandelt, um auch Integerarrays zu behandeln. Ich poste mal beide Codes, erst als char (das funktioniert ja), dann für int. Kann mir jemand weiterhelfen?

#include <stdio.h>
#include <stdlib.h>

typedef const char *SetType;
typedef int bool;

typedef struct setStruct {
    int     count;
    SetType *elements;
    void   (*printer)(SetType );
    bool    nlAfterElements;
} *Set;

/* Could probly use same struct as above for this */
typedef struct powerSetStruct {
    int     count;
    Set     *elements;
    void    (*printer)(Set);
    bool    nlAfterElements;
} *PowerSet;

void PrintSet( Set s);

PowerSet GetPowerSet( Set set)
{
    int ix, n, j;
    int max = 1<<set->count;            // Assuming count < 32

    PowerSet ps = (PowerSet)malloc( sizeof(struct powerSetStruct));

    if (ps) {
        ps->elements = (Set*)malloc( max*sizeof(Set));
        ps->count = max;
        ps->printer = PrintSet;
        ps->nlAfterElements = 1;

        for (ix=0; ix<max; ix++) {
            int setsize = 0;
            Set se = (Set)malloc(sizeof(struct setStruct));

            for (j=0; j<set->count; j++) 
                if (ix & (1<<j)) setsize++;
            if (setsize > 0) {
                se->elements = (SetType *)malloc(setsize *sizeof(SetType));
                n = 0;
                for (j=0; j<set->count; j++) {
                    if (ix & (1<<j)) {
                        se->elements[n] = set->elements[j];
                        n++;
                    }
                }
            }
            else {
                printf("No elements in set %d\n", ix);
                se->elements = NULL;
            }
            se->count = setsize;
            se->printer = set->printer;
            se->nlAfterElements = set->nlAfterElements;
            ps->elements[ix] = se;
        }
    }
    return ps;
}

void PrintSet( Set s)
{
    const char *sep = "";
    int ix;
    printf("{");
    for (ix=0; ix<s->count; ix++) {
        printf("%s ", sep); 
        s->printer(s->elements[ix]);            
        sep = (s->nlAfterElements)? ",\n " :",";
    }
    printf(" }");
}

void PrintString( const char *str)
{
    printf("%s", str);
}

int main()
{
    const char *eles[] = {"Red","Grn","Blu","Ylo"};
    struct setStruct aSet = { 4, eles, PrintString, 0 };
    PowerSet p = GetPowerSet( &aSet);

    PrintSet(&aSet); printf("\n");
    PrintSet( (Set)p ); printf("\n");
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

typedef int SetType;
typedef int bool;

typedef struct setStruct {
    int     count;
    SetType *elements;
     void   (*printer)(SetType );
    bool    nlAfterElements;
} *Set;

/* Could probly use same struct as above for this */
typedef struct powerSetStruct {
    int     count;
    Set     *elements;
    void    (*printer)(Set);
    bool    nlAfterElements;
} *PowerSet;

void PrintSet( Set s);

PowerSet GetPowerSet( Set set)
{
    int ix, n, j;
    int max = 1<<set->count;            // Assuming count < 32

    PowerSet ps = (PowerSet)malloc( sizeof(struct powerSetStruct));

    if (ps) {
        ps->elements = (Set*)malloc( max*sizeof(Set));
        ps->count = max;
        ps->printer = PrintSet;
        ps->nlAfterElements = 1;

        for (ix=0; ix<max; ix++) {
            int setsize = 0;
            Set se = (Set)malloc(sizeof(struct setStruct));

            for (j=0; j<set->count; j++) 
                if (ix & (1<<j)) setsize++;
            if (setsize > 0) {
                se->elements = (SetType *)malloc(setsize *sizeof(SetType));
                n = 0;
                for (j=0; j<set->count; j++) {
                    if (ix & (1<<j)) {
                        se->elements[n] = set->elements[j];
                        n++;
                    }
                }
            }
            else {
                printf("No elements in set %d\n", ix);
                se->elements = NULL;
            }
            se->count = setsize;
            se->printer = set->printer;
            se->nlAfterElements = set->nlAfterElements;
            ps->elements[ix] = se;
        }
    }
    return ps;
}

void PrintSet( Set s)
{
    int sep = 0;
    int ix;
    printf("{");
    for (ix=0; ix<s->count; ix++) {
        printf("%i ", sep); 
        s->printer(s->elements[ix]);            
        sep = (s->nlAfterElements)? ",\n " :",";
    }
    printf(" }");
}

void PrintString( int str)
{
    printf("%i", str);
}

int main()
{
    int i;
    int eles[] = {1,2,3,4};
    struct setStruct aSet = { 4, eles, 0 };
    PowerSet p = GetPowerSet( &aSet);

    PrintSet(&aSet); printf("\n");
    PrintSet( (Set)p ); printf("\n");
    return 0;
}

Wutz

Das schreit alles nach Templates oder zumindest nach C++.
Aber wir sind hier ja bei C.

Dein Ausgangscode ist nicht konsequent,
SetType steht nicht überall, wo es verwendet wird, also

void PrintString( SetType str)

und

SetType eles[] = ...

und bei PrintSet muss const char* natürlich bleiben.
Dann sollte es klappen.
Das ändert aber nichts daran, dass dies kopierter Code ist und allenfalls für den Hausgebrauch ausreichend.

Mir ist nicht ganz klar, was gemacht werden soll, aber du könntest doch mit void * hantieren, um mehrere Typen zu unterstützen?

Wutz

Natürlich kannst du void verwenden, der Compiler ist dann zufrieden.
Aber dann hast du Probleme beim Rückcasten, du hast keinen (wie bei C++) Kontext, aus dem du bestimmen kannst, wohin du casten musst.

Außerdem wird die Initialisierung schwierig

void eles[] = { ...,??? };