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 00011122233344455566677777Meine 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
EukalyptusDann 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.:
00000000000000000134444777so dürfte es zb. aussehen:
00000000000000000134455667
00000000000000000134444444Gibt 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.:
00000000000000000134444777so dürfte es zb. aussehen:
00000000000000000134455667
00000000000000000134444444Gibt es eine möglichkeit dieses Manko zu beseitigen?
Viele Grüße
EukalyptusEDIT:
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.