Rekursion: mögliche Reihenfolgen finden

Korhil

Hallo alle zusammen,

ich habe ein Problem bei dem ich leider gerade ins Stocken gekommen bin:

Eine beliebige Anzahl von Elementen soll nach bestimmten Kriterien in eine sinnvolle Reihenfolge gebracht werden. Allerdings bin ich nicht nur an einer Kombination interessiert sondern an allen möglichen Kombinationen.

Für eine Kombination habe ich auch eine Lösung, weiß allerdings gerade nicht so richtig weiter, wie ich alle Lösungen erhalten kann:

int ElementeKombinieren(int Element, 
                        int AnzahlElemente, 
                        int Liste[MAX_ANZAHL],
                        int Index)
{
    if (Index == AnzahlElemente)
        return 1;    // Kombination fertig

    if (Element == AnzahlElemente)
    {
        Liste[Index] = -1;    //Leerwert setzen
        return 0;    // Kombination falsch
    }

    if ( BedingungenErfuellt(Liste, AnzahlElemente))
        ElementeKombinieren(0,AnzahlElemente, Liste, Index+1);
    else
        ElementeKombinieren(Beruf+1,AnzahlElemente, Liste, Index);

}

...

ElementeKombinieren(0,Aanzahl,Liste,0);    // Aufruf der Funktion aus dem
                                           // Programm heraus

Die Funktion BedingungenErfuellt() übernimmt die Kontrolle der Liste.

^^ du willst alle vertauschungen haben (z.b. aus 123 wird 123,132,321,312,213,231), oder wie?

Korhil

Ja genau,

nur halt unter Beachtung der Bedingungen, die in der Funktion BedingungenErfuellt() überprüft werden.

Hab mir gerade mal überlegt, ob die Lösung sein könnte, anstatt dem

return 1;

die Liste anderweitig zu speichern und

return 0; //Fehler

zurück zu geben ?

EDIT: Da ist jetzt noch ein Denkfehler drin, sehe aber leider gerade vor lauter Bäumen den Wald nicht mehr.

Korhil schrieb:

Ja genau,

google mal: 'permutation filetype:c', da findeste bestimmt was (besser nicht-rekursives). ich hoffe, deine arrays sind nicht allzu gross, denn sonst haste 'ne astronomische anzahl von vertauschungen, bei der sich dein computer 'nen wolf rechnen wird.

Korhil

Danke für den Tipp,

hab etwas gefunden, was mir bei meinem Problem weiter geholfen hat:

int ElementeKombinieren(int Index)
{
    int i;

    RekLvlElemente++;
    ReihenfolgeElemente[Index-1] = RekLvlElemente;

    if (RekLvlElemente == AnzahlElemente)
    {
        printf("\n");
        for (i=0; i < AnzahlElemente; i++)
        {
            printf(" %d ",ReihenfolgeElemente[i]);
        }
        printf("\n"); 
    }
    for (i=1; i <= AnzahlElemente; i++)
    {
        if (!ReihenfolgeElemente[i-1])
            ElementeKombinieren(i);
    }

    RekLvlElemente--;
    ReihenfolgeElemente[Index-1] = 0;
    return 0;
}

Bei der Ausgabe muss ich jetzt noch meine Bedingungsüberprüfung einfügen, dann ist der teil zumindest schon einmal fertig.

Zu deiner Hoffnung/Befürchtung kann ich nur soviel sagen, das Programm wird wohl ein wenig länger brauchen:

Derzeit sind es 8 Elemente. Zu jedem Ergebnis muss ich nochmals so eine reukusive Funktion mit 3 Elementen aufrufen, die wiederum je 10 Elemente durchkombiniert (...).

Ich glaub, ich muss schon mal bei der NASA anfragen, ob die ein wenig Rechenleistung übrig haben