Alle möglichen Zahlenkombinationen in Reihenfolge



  • Hallo,

    mein Anliegen ist folgendes:

    Ich habe vor ein Programm zu schreiben, dass mir Felder, die aus 26 Elementen bestehen, mit alle möglichen Zahlenkombinationen von 0-7 ausgibt.
    Die Haken dabei sind das die Zahlen nicht kleiner werden dürfen und in Reihenfolge sein müssen (also keine Zahl darf übersprungen werden und das erste Feldelement muss 0 sein). Dagegen müssen nicht immer alle 7 Zahlen vorhanden sein.

    Hier noch ein paar Beispiele wie die Felder aussehen dürfen:
    Feld_a 00000000000000000000000000
    Feld_b 00000000000000000000000111
    Feld_c 00011112233333444445555566
    Feld_d 0000000000122222222222223
    Feld_e 00111111111111111111111111111
    Feld_f 00011122233344455566677777

    Meine bisherigen Versuche blieben leider ohne Erfolg.

    Vielleicht könnte mir einer von euch behilflich sein?
    Lösungsvorschläge oder Programmcode (am liebsten in c) würden mir wirklich weiterhelfen!

    Viele Grüße

    Eukalyptus



  • Willst du am ende alle möglichen Zahlenkombinationen durchlaufen haben?

    sprich:
    von 000000000000...0000
    bis 012345677777...777
    ? Oder hab ich dich falsch verstanden?

    Zeig doch mal deine bisherigen Versuche/Überlegungen. Vuelleicht biste ja schon auf'm richtigen weg. 🙂



  • Lösungsvorschlag: Rekursiv, und zwar folgendermaßen:
    Du übergibst den Index der Zahl, die als nächstes generiert werden soll, und das Minimum der Zahlen, die noch kommen dürfen. Beispiel, du hast schon die Folge 00134445, dann übergibst du Index 8 und Minimum 5. Die Funktion schreibt jetzt an diesen Index nacheinander alle noch möglichen Zahlen (also 5, 6, 7) und ruft danach jeweils sich selbst mit einem um 1 erhöhten Index und ggf. dem neuen Minimum auf. Ist der Index 26, generiert sie nichts mehr, sondern gibt das aus, was sie hat.
    Die Datenhaltung würde ich irgendwie über ein statisches Array oder so regeln.



  • Lupo4u2 schrieb:

    Willst du am ende alle möglichen Zahlenkombinationen durchlaufen haben?

    sprich:
    von 000000000000...0000
    bis 012345677777...777
    ? Oder hab ich dich falsch verstanden?

    Zeig doch mal deine bisherigen Versuche/Überlegungen. Vuelleicht biste ja schon auf'm richtigen weg. 🙂

    Hallo,

    erstmal thx für die schnelle Antwort.

    Ja genau so, alle möglichen Kombinationen von 000000000000...0000 bis 012345677777...777.

    Meine bisherigen Versuche machte ich mit verschachtelten Schleifen, doch entweder wurden nicht alle Kombinationen generiert oder alle möglichen Kombinationen ohne Reihenfolge generiert.

    Viele Grüße
    Eukalyptus



  • Eukalyptus schrieb:

    Meine bisherigen Versuche machte ich mit verschachtelten Schleifen, doch entweder wurden nicht alle Kombinationen generiert oder alle möglichen Kombinationen ohne Reihenfolge generiert.

    Viele Grüße
    Eukalyptus

    Dann tu nochmal Bashars Vorschlag gucken.
    🙂



  • Bashar schrieb:

    Lösungsvorschlag: Rekursiv, und zwar folgendermaßen:
    Du übergibst den Index der Zahl, die als nächstes generiert werden soll, und das Minimum der Zahlen, die noch kommen dürfen. Beispiel, du hast schon die Folge 00134445, dann übergibst du Index 8 und Minimum 5. Die Funktion schreibt jetzt an diesen Index nacheinander alle noch möglichen Zahlen (also 5, 6, 7) und ruft danach jeweils sich selbst mit einem um 1 erhöhten Index und ggf. dem neuen Minimum auf. Ist der Index 26, generiert sie nichts mehr, sondern gibt das aus, was sie hat.
    Die Datenhaltung würde ich irgendwie über ein statisches Array oder so regeln.

    Hallo,

    auch dir thx für die flotte Antwort.

    Das ganze Rekursiv zu lösen finde ich intressant, aber leider steige ich nicht ganz dahinter. Ich möchte ja jeweils in einem Index nur eine Zahl stehen haben (0...7) und leider verstehe ich nicht wie mir diese möglichkeit alle möglichen kombinationen liefert.
    Könntest du das evtl. noch vertiefen?

    Viele Grüße
    Eukalyptus



  • etwa so:

    void allOrderedCombinations(int startIndex, int min) {
      static int field[26]
      if (startIndex == 26)
        // field ausgeben ...
      else
        for (int i = min; i <= 7; ++i) {
          field[startIndex] = i;
          allOrderedCombinations(startIndex + 1, i);
        }
    }
    
    // Anfangsaufruf:
    allOrderedCombinations(0, 1);
    


  • Bashar schrieb:

    etwa so:

    void allOrderedCombinations(int startIndex, int min) {
      static int field[26]
      if (startIndex == 26)
        // field ausgeben ...
      else
        for (int i = min; i <= 7; ++i) {
          field[startIndex] = i;
          allOrderedCombinations(startIndex + 1, i);
        }
    }
    
    // Anfangsaufruf:
    allOrderedCombinations(0, 1);
    

    Huhu,

    erstmal danke für deine mühe.

    Habe das Programm gerade getestet und schein gut zu funktionieren!
    Werde mich damit morgen mal näher befassen.

    Viele Grüße
    Eukalyptus



  • Huhu,

    leider habe ich noch ein Problem mit dem Programm:

    Es werden teilweise Zahlen übersprungen zb.:
    00000000000000000134444777

    so dürfte es zb. aussehen:
    00000000000000000134455667
    00000000000000000134444444

    Gibt es eine möglichkeit dieses Manko zu beseitigen?

    Viele Grüße
    Eukalyptus



  • Eukalyptus schrieb:

    Huhu,

    leider habe ich noch ein Problem mit dem Programm:

    Es werden teilweise Zahlen übersprungen zb.:
    00000000000000000134444777

    so dürfte es zb. aussehen:
    00000000000000000134455667
    00000000000000000134444444

    Gibt es eine möglichkeit dieses Manko zu beseitigen?

    Viele Grüße
    Eukalyptus

    EDIT:
    so dürfte es zb. aussehen:
    00000000000000000123445566
    00000000000000000123444444



  • Sorry, da hab ich wohl die Spec etwas zu meinen Gunsten ausgelegt 😉 Hier die korrigierte Version, die Grundidee ist ähnlich. Der Parameter startIndex ist noch derselbe, aus min wurde max und bedeutet jetzt, welche Zahl zuletzt ausgegeben wurde (also das Maximum der bisher ausgegebenen Zahlen). Statt jetzt alle größeren Zahlen auszugeben dürfen wir nur das max nochmal ausgeben oder den nächstgrößeren Wert. Bzw. beides, wir suchen ja alle Kombinationen.

    void allOrderedCombinations(int startIndex, int max) {
      static int field[26]
      if (startIndex == 26)
        /* field ausgeben ... */
      else {
        if (max >= 0) {
          field[startIndex] = max;
          allOrderedCombinations(startIndex + 1, max);
        }
        if (max < 7)
          field[startIndex] = max + 1;
          allOrderedCombinations(startIndex + 1, max + 1);
        }
      }
    }
    /* Aufruf jetzt: */
    allOrderedCombinations(0, -1);
    

    Die -1 ist etwas häßlich, man könnte das Programm so transformieren, dass man da 0 übergeben muss, aber das verwässert die Verständlichkeit des Algorithmus'.



  • Huhu,

    nochmals danke für deine mühe.

    In dieser Form funktioniert das Programm bei mir leider nicht. Deshalb fügte ich nach der Ausgabe des Feldes noch folgendes hinzu:

    startIndex = startIndex-1;
    

    Jetzt scheint es gut zu funktionieren!

    Viele Grüße
    Eukalyptus



  • Hallo,
    dass das was bringt würde ich bezweifeln. Ich hatte die geschweiften Klammern um den else-Block vergessen (das kommt davon, wenn man es in C++ schreibt und dann ohne nochmal zu testen eine C-Version postet). Siehe edit im Vorposting.



  • Bashar schrieb:

    Hallo,
    dass das was bringt würde ich bezweifeln. Ich hatte die geschweiften Klammern um den else-Block vergessen (das kommt davon, wenn man es in C++ schreibt und dann ohne nochmal zu testen eine C-Version postet). Siehe edit im Vorposting.

    huhu,

    tatsächlich, hab ich übersehen.
    Aber der (die) Compiler meldete(n) auch keinen Fehler. Nur nach dem ersten Durchlauf lief die Indexvariable über weil sie nicht zurückgesetzt wurde, dies behob ich dann indem ich sie nach der Ausgabe des Feldes manuell um 1 verringerte und so läuft das Programm auch ohne die die geschweifte Klammer^^ Hier mal der Code:

    void allOrderedCombinations(int startIndex, int max) {                 
    
      static int field[26];                                                
      if (startIndex == 26){                                               
        for (int x = 0; x != 26; ++x) {                                  
    	  cout << field[x];
    	 }
    	 cout << endl;
             startIndex = startIndex-1;
      }
      else
        if (max >= 0) {                                                  
          field[startIndex] = max;                                       
          allOrderedCombinations(startIndex + 1, max);
        }
    	if (max < 7) {                                                
          field[startIndex] = max + 1;
          allOrderedCombinations(startIndex + 1, max + 1);                 
        }
    }
    
    int main(int argc, char* argv[])
    {
    allOrderedCombinations(0, -1);                                          
    getch();
    return 0;
    }
    

    Viele Grüße
    Eukalyptus



  • Huhu,

    so hab jetzt mal den verbesserten Code versucht und klappt!
    Jetzt pack ich erstmal die 700k kombinationen in jeweils ein feld...

    Viele Grüße
    Eukalyptus



  • Ich hoffe mit "verbessert" meinst du nicht deinen geflickten Code. Dass der funktioniert ist nämlich blanker Zufall 🙂



  • Bashar schrieb:

    Hallo,
    dass das was bringt würde ich bezweifeln. Ich hatte die geschweiften Klammern um den else-Block vergessen (das kommt davon, wenn man es in C++ schreibt und dann ohne nochmal zu testen eine C-Version postet). Siehe edit im Vorposting.

    Geschweifte Klammern um if/else Blöcke verhalten sich bei C und C++ ja auch so verschieden. 🤡



  • Bashar schrieb:

    Ich hoffe mit "verbessert" meinst du nicht deinen geflickten Code. Dass der funktioniert ist nämlich blanker Zufall 🙂

    Huhu,

    ne meine natürlich den "richtig verbesserten"^^.

    Ganz Zufällig war das auch nicht, hab dein erstes Programm und das neue (das nicht funktionierte) durch den Debugger laufen lassen und dabei ist mir aufgefallen das der Index immer weiterläuft wo er hingegen im anderen Programm um 1 reduziert wurde.
    Funktionieren tut die "geflickte" Version trozdem nicht 100%, denn sie liefert mehr Kombinationen als nötig.

    Jetzt kam ich inzwischen gut voran mit der Funktionalität des Programmes und möchte mich nochmal für deine schnelle und kompetente Hilfe bedanken.

    Falls weitere Fragen auftreten melde ich mich.

    Viele Grüße
    Eukalyptus



  • ohne rekursion gehts einfacher:

    void ordered_combinations (void)
    {
        int field[26] = {0};
        int idx = 25;
        for (;;)
        {
            while (field[idx-1] < field[idx])
                idx--;
            field[idx]++;
            idx = 25;
            print (field);  // <-- ausgabe
        }
    }
    

    ^^fehlt nur 'ne abbruchbedingung, aber bei 26 ints dauert das ja auch etwas.
    🙂


Log in to reply