Alle Möglichkeiten ausgeben.

Hi,

wir haben von der Schule folgende Aufgabenstellung bekommen:

Es sollen alle Möglichkeiten (Kombinationen) eines Strings (Maximal 6 Zeichen länge + Nullterminierung) ausgegeben werden. Alle erlaubten Zeichen werden in einer Zeichentabelle definiert.

Ich habe mir da auch etwas zusammen gestellt, doch irgendwie kommen nicht alle Kombinationen raus. Am Ende habe ich nur noch Rauten.

Hier mein Code:

#include <iostream>

int main(int argc, char *argv[])
{
    const char characters [38] =
    {
        // Zahlen
        '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 

        // Buchstaben klein
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 
        'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 
        'u', 'v', 'w', 'x', 'y', 'z',

        // Sonderzeichen
        ' ', '#',
    };

    char buffer[] = "000000";    
    for (unsigned long i=0; i<strlen (buffer); ++i)
    {
        for (unsigned long j=0; j<38; ++j)
        {
            buffer[i] = characters[j];
            std::cout << buffer << std::endl;
        }
    }

    system("PAUSE");
    return EXIT_SUCCESS;
}

Ich bin mir sicher, ich habe nur etwas übersehen, weiß aber nicht was.

Ich danke schon mal im voraus für jegliche Hilfe

bye

CStoll

Deine gesamte Schleifenstruktur entspricht nicht der Anforderung "alle Kombinationen" - du rotierst nacheinander alle Stellen einmal von 0 ('0') bis 38 ('#') durch, anstatt alle beliebigen Kombinationen durchzulaufen.

Als Ansatz könntest du eine rekursive Funktion zum Zusammenbau der Kombinationen verwenden:

void combi(char* data, int pos)
{
  if(pos==strlen(data)
    cout<<data<<endl;
  else
  {
    for(int i=0;i<38;++i)
    {
      data[pos]=characters[i];
      combi(data,pos+1);
    }
  }
}

//im Hauptprogramm
char buffer[]="......";
combi(buffer,0);

Alternativ kannst du deine Symbole auch als Ziffern in einem 38'er Zahlensystem interpretieren und der Reihe nach alle Zahlen von 0 bis 3010936383 (=38⁶-1) in dieses System umrechnen.

schrankwand

Ist doch klar. Du setzt für die erste Stelle alle möglichen Zeichen einmal ein, setzt dann für die 2. Stelle alle möglichen Zeichen einmal ein, usw. Jedoch ist zu bedenken, dass alle Stellen vor der aktuellen Stelle immer das letzte Zeichen und alle danach immer das erste Zeichen erhalten werden.

schrankwand

Rekursive Funktionsaufrufe gelten allgemein als schlechte Praxis da sie den Callstack anwachsen lassen, was zum einen langsam ist und zum anderen ab einer gewisen tiefe einen Stackoverflow erzeugen kann.

Alternativ könntest du auch noch mit Sprungmarkierungen (goto) arbeiten.

CStoll

schrankwand schrieb:

Rekursive Funktionsaufrufe gelten allgemein als schlechte Praxis da sie den Callstack anwachsen lassen, was zum einen langsam ist und zum anderen ab einer gewisen tiefe einen Stackoverflow erzeugen kann.

Bei einer maximalen Rekursionstiefe von 6 dürfte DAS noch kein Problem sein. Aber du kannst stattdessen auch gerne 6 ineinander verschachtelte for()-Schleifen verwenden, wenn du meinst, daß das eleganter aussieht

Alternativ könntest du auch noch mit Sprungmarkierungen (goto) arbeiten.

Wenn du schon Rekursion verteufelst, solltest du das Wort "goto" nicht einmal in den Mund nehmen.

LordJaxom

schrankwand schrieb:

Alternativ könntest du auch noch mit Sprungmarkierungen (goto) arbeiten.

Sprungmarkierungen gelten allgemein als schlechte Praxis da sie die Funktionen anwachsen lassen, was zum einen unübersichtlich ist und zum anderen ab einer gewisen Verschachtelungstiefe unerwünschte Nebenwirkungen haben kann.

*SCNR*

Hi Leute, sorry war lange nicht da (Urlaub :)) und wollte mich noch mal für die freundliche Hilfe bedanken! Es hatte wunderbar funktioniert.

Eine Frage hätte ich aber noch: CStoll, Du sagstest "Rekursionstiefe von 6" ist das noch egal. Aber was ist wenn ich Kombinationen mit einer Länge von hmn... sagen wir 32 durchgehen möchte? Was für ein Ansatz ist hier der Beste? Denke, dass da der Callstack evtl. flöten gehen kann.

Nochmals danke im voraus

Bashar

schrankwand schrieb:

Rekursive Funktionsaufrufe gelten allgemein als schlechte Praxis

Falsch.

Aber was ist wenn ich Kombinationen mit einer Länge von hmn... sagen wir 32 durchgehen möchte?

Ab Größenordnungen von hunderttausend oder millionen wirds vielleicht kritisch, aber nicht bei 32.

CStoll

Der Stack hält schon einiges aus (im MSVC ist der per Default 1MB groß), also brauchst du dir da keine Sorgen machen. (Probleme bekommst du erst, wenn du um (grob geschätzt) 100000 Zeichen verarbeiten willst - oder wenn du eine unkontrollierte Rekursion aufgebaut hast)

(und der Vorteil des rekursiven Ansatzes ist, daß die Funktion für beliebige Textlängen anwendbar ist - bei verschachtelten Schleifen mußt du die Größe zur Compilezeit festlegen)

Cool vielen dank Also kann ich dann ja beruhigt eine Länge von 32 haben und eine 256 Zeichen große Zeichentabelle haben Danke!