ich weiß nicht ob ich hier richtig bin aber ich versuchs mal:
ich benötige einen Zähl-Algorithmus bei dem die Felder in einem Array durchgezählt werden sollen, von einer minimalen Zahl im Feld bis zu einer maximalen Zahl im Feld, aber die Summe über alle Felder im Array konstant bleiben muss. Beispiel:
4 Felder und gewünschte Summe ist 6 und mögliche Zahlen in den Feldern sind 1 und 2, also gibt es 6 Kombinationen:
ich hab erstmal eine simplen Zähl-Algorithmus programmiert der (für dieses Beispiel) alle 16 möglichen Kombinationen durchzählt und jedes mal aufsummiert und prüft ob die Summe passt, das ist natürlich extrem ineffizient (in meinem realem Problem sind die Kombinationsmöglichkeiten deutlich zahlreicher, mein Beispiel hier ist kras vereinfacht, und da ist Brute-Force keine gute Lösung).
Ich suche also einen Zähl-Algorithmus der mein Problem elegant lößt aber ich komme auf keine Lösung, irgendwie scheint mein Hirn aktuell ein Problem mit Mathematik zu haben.
Du könntest von der Gesamtsumme rückwärts zählen. Wenn 0 oder unter null kannst du abbrechen. Im Beispiel wenn schon in den ersten 3 Feldern eine zwei steht. Ebenso wenn die Restzahl zu klein ist (die ersten 3 Felder 1)
Beim Beispiel bringt das nicht viel, aber bei vielen Feldern und großen Möglichkeitsbereichen kann das schon einiges ausmachen.
Wenn die Zellen nicht zufällig gefüllt und zu testen sind, sondern nacheinander alle Möglichkeiten, kannst du damit von vornherein ganze Blöcke ausschließen.
Ich würde eine Tiefensuche machen, jede Ebene steht für eine Ziffer, der Wurzelknoten für die erste Ziffer, Blätter für die letzte.
Unterwegs die Quersumme mitrechnen, dann ist die letzte Ebene einfach.
Zum nächsten Zählerinkrement kommst du folgendermaßen:
du erhöhst dir vorletzte Stelle um 1. Tiefensuche auf niedrigeren Ebenen liefert dir die letzte Stelle (Rest zur Quersumme).
Wenn erhöhen nicht mehr geht oder die Tiefensuche keine Lösung liefert (Quersumme zu groß), dann musst du eine weitere Stelle nach vorne gehen und die um eins erhöhen. Tiefensuche ab da liefert dir wieder die kleinstmögliche passende Kombination.
Wenn es dann immer noch keine Lösung gibt: eine Stelle weiter nach vorne etc.
Nachtrag:
Jobst Q. hat natürlich recht, untaugliche Bäume so früh wie möglich zu überspringen (Pruning).
Es bietet sich an, das Alphabet auf 0..x zu ändern (und die Quersumme entsprechen anzupassen - ist ja nur eine Verschiebung). Dann musst du für das Pruning nur die "Quersumme zu groß"-Prüfung machen.
void find_combinations(int fields[], int num_fields, int sum, int current_sum, int current_field) {
4
if (current_field == num_fields) {
5
if (current_sum == sum) {
6
printf("Kombination gefunden: ");
7
for (int i = 0; i < num_fields; i++) {
8
printf("%d ", fields[i]);
9
}
10
printf("\n");
11
}
12
return;
13
}
14
15
// Versuche alle möglichen Werte für das aktuelle Feld
16
for (int i = 1; i <= 2; i++) {
17
fields[current_field] = i;
18
find_combinations(fields, num_fields, sum, current_sum + i, current_field + 1);
19
}
20
}
21
22
int main() {
23
int fields[4];
24
find_combinations(fields, 4, 6, 0, 0);
25
return 0;
26
}
In diesem Code wird die rekursive Funktion "find_combinations" verwendet, um alle möglichen Kombinationen von Feldern zu finden, die die Summe 6 ergeben. Die Funktion nimmt als Parameter das Array der Felder, die Anzahl der Felder, die gewünschte Summe, die aktuelle Summe und das aktuelle Feld. Innerhalb der Funktion wird überprüft, ob alle Felder gezählt wurden. Wenn ja, wird überprüft, ob die aktuelle Summe der gewünschten Summe entspricht. Wenn ja, wird die aktuelle Kombination ausgegeben. Wenn nein, wird die Funktion beendet. Wenn nicht alle Felder gezählt wurden, werden alle möglichen Werte für das aktuelle Feld ausprobiert und die Funktion erneut aufgerufen.
Genau! Das ist eine Tiefensuche, rekursiv programmiert.
Die Traversiert einmal den kompletten Baum und liefert alle gültigen Kombinationen in der richtigen Reihenfolge.
Dass muss der TO jetzt erweitern, so dass nicht nur 1 und 2 als gültige Symbole verwendet werden.
Dann gibt es noch Optimierungsmöglichkeiten, z.B. die genannten Suchbaumeinschränkungen, wenn in der Rekursion weiter unten keine Lösungen mehr möglich sind.
Ebenso kann man die Rekursion entsprechend umbauen, dass nicht alle Lösungen ausgegeben werden sondern nur die nächste gesucht wird.
Eine Möglichkeit, Partitionen zu bestimmen ist rekursiv:
Um zum Beispiel 6 in 1en und 2en zu zerlegen, nimmt man Partitionen von 4 und nimmt zur Menge der Teile 2 hinzu, oder man nimmt Partitionen von 5 und nimmt zur Menge der Teile 1 hinzu.
printf ("n = %d in %d Summanden:\n", n, n_summands);
55
decompose (6, 0, 4); // Immer 4 summanden
56
57
printf ("n = %d in beliebig viele Summanden:\n", n);
58
decompose (6, 0, -1);
59
60
printf ("n = %d in beliebig viele Summanden (monoton wachsend):\n", n);
61
decompose (6, 0, -2);
62
}
Ausgabe
1
n = 6 in 4 Summanden:
2
1 1 2 2
3
1 2 1 2
4
1 2 2 1
5
2 1 1 2
6
2 1 2 1
7
2 2 1 1
8
n = 6 in beliebig viele Summanden:
9
1 1 1 1 1 1
10
1 1 1 1 2
11
1 1 1 2 1
12
1 1 2 1 1
13
1 1 2 2
14
1 2 1 1 1
15
1 2 1 2
16
1 2 2 1
17
2 1 1 1 1
18
2 1 1 2
19
2 1 2 1
20
2 2 1 1
21
2 2 2
22
n = 6 in beliebig viele Summanden (monoton wachsend):
23
1 1 1 1 1 1
24
1 1 1 1 2
25
1 1 2 2
26
2 2 2
So wie der Code steht, bestimmt er nur Partitionen, die aus Summanden aus parts[] bestehen, hier also 1 und 6. Mann man beliebige natürliche Summanden zulassen will, braucht's ne kleine Erweiterung.
ich benötige einen Zähl-Algorithmus bei dem die Felder in einem Array
durchgezählt werden sollen, von einer minimalen Zahl im Feld bis zu
einer maximalen Zahl im Feld, aber die Summe über alle Felder im Array
konstant bleiben muss.
Du willst also gar nicht zählen.
Du willst permutieren.
Dafür gibt es viele fertige Funktionen.
Dann brauchst du bloss noch EINE Arraybelegung vorzugeben, die mit den erlaubten Zahlen deine Summe ergibt.
Und die kann z.B. im Array zuerst die grösste Zahl speichern, hinten die kleinste, und dazwischen den Rest verteilen. Wenn es 6 als Summe von 1 und 2 im Feld sein soll gibt es halt nur 2,2,1,1
Wenn es 10 sein soll und alle Ziffern von 0 bis 9 gibt es
kleinstmögliche Zahl (ist in reality meist 2 oder 3, muss größer als 0
sein)
größtmögliche Zahl (ist meist im Rahmen von 20 bis 30 kann aber auch
größer sein)
Die Zahl der Parameter kann man reduzieren, indem man die kleinstmögliche Zahl als Offset abzieht und erst zur Ausgabe wieder dazu nimmt. Dann hat man immer einen Bereich von 0 bis x.
Bei einem Bereich von 20 bis 30 muss aber die Zahl der Felder beschränkt werden, sonst wird die Zahl der Kombinationen (Bereich hoch Felder) astronomisch.
ich benötige einen Zähl-Algorithmus bei dem die Felder in einem Array
durchgezählt werden sollen, von einer minimalen Zahl im Feld bis zu
einer maximalen Zahl im Feld, aber die Summe über alle Felder im Array
konstant bleiben muss.
Du willst also gar nicht zählen.
Du willst permutieren.
Dafür gibt es viele fertige Funktionen.
Dann brauchst du bloss noch EINE Arraybelegung vorzugeben, die mit den
erlaubten Zahlen deine Summe ergibt.
Und die kann z.B. im Array zuerst die grösste Zahl speichern, hinten die
kleinste, und dazwischen den Rest verteilen. Wenn es 6 als Summe von 1
und 2 im Feld sein soll gibt es halt nur 2,2,1,1
Wenn es 10 sein soll und alle Ziffern von 0 bis 9 gibt es
9,1,0,0
8,2,0,0
8,1,1,0
Und was ist mit
9,0,1,0
9,0,0,1
8,0,2,0
8,0,0,2
...
Vollständig ist die so generierte Liste jedenfalls nicht.
Aber der Ansatz, nicht alle möglichen Kombinationen durch zu testen, sondern zutreffende Kombinationen systematisch abzuändern, ist sehr gut. Ob da Permutation noch der passende Ausdruck ist, ist unwesentlich. Eine klassische Permutation ist es wohl nicht.
Sehr praktisch ist, dass man eine solche Funktion rekursiv anwenden kann.
Im Beispiel um alle Kombinationen mit 9 im ersten Feld zu finden, ruft man die Funktion mit Felder=3, Quersumme=1, Bereich = 2 (0 bis 1) auf.
Bei 8 am Anfang mit Felder=3, Quersumme=2, Bereich = 3 (0 bis 2).
Bei 7 am Anfang mit Felder=3, Quersumme=3, Bereich = 4 (0 bis 3).
usw.
Ja, das sieht sehr interessant aus, aber da werde ich ne Weile für brauche bis ich da durchgestiegen bin. Beim schnellen überfliegen des Wikipedia-Artikel hab ich leider keine Lösung für effizientes ermitteln gesehen. Mein Problem ist das die Gesamtanzahl der möglichen Muster (Größe-Alphabet hoch Anzahl-Felder) im Bereich 10^9 bis 12^12 liegt (und wir haben hier eine Variante wo die Komplexität für Brute-Force-Durchzählen bei etwa 10^20 ist, das ist auch für einen modernen PC mit GHz-CPU zu viel so das wir das bis jetzt noch nichtmal probiert haben).
Einen rekursiven Algorithmus möchte ich vermeiden da ich kaum abschätzen kann wie viele Rekursionsebenen es werden könnten und man da ja aufpassen muss das der Stack nicht ausgeht.
von Michael B. schrieb:
Du willst also gar nicht zählen.
Du willst permutieren.
Ob man das nun Permutation nennt ist mir egal aber ich hatte die Vermutung das wenn ich eine Zahl um eins erhöhe da ich dann eine andere Zahl um eins verringern muss das es da eventuell einen Algorithmus gibt der genau das leistet und somit alle "gültigen" Varianten findet ohne dafür Brute-Force-Durchzählen benutzen zu müssen.
von Michael B. schrieb:
Wenn es 10 sein soll und alle Ziffern von 0 bis 9 gibt es
9,1,0,0
8,2,0,0
...
in diesem Beispiel gibt es 282 "gültige" Kombinationen aber eben 10000 simple Zähl-Möglichkeiten. Leider habe ich nichtmal eine Methode mit der ich die 282 ausrechnen kann, aktuell muss ich meinen Algorithmus einfach laufen lassen wenn ich auch nur wissen will wie viele gültige Möglichkeiten es gibt.
Hat dafür schonmal jemand eine Idee?
von Tilo R. schrieb:
Dann gibt es noch Optimierungsmöglichkeiten, z.B. die genannten
Suchbaumeinschränkungen, wenn in der Rekursion weiter unten keine
Lösungen mehr möglich sind.
In meiner aktuellen Lösung hab ich schon einige Optimierungen so das wenn die gewünschte Quersumme schon in den ersten paar Felder erreicht/überschritten wird das dann nicht mehr bis zum letzten Feld stur inkrementiert wird sondern schon in einem vorderen Feld und die nachfolgenden Felder alle wieder auf den minimalen Wert gesetzt werden. Ich kann nicht genau sagen wie viel das einspart aber ich war etwas Zeit damit beschäftigt sicher zu beweisen das mir dadurch keine "gültigen" Kombinationen verloren gehen.
von Jobst Q. schrieb:
Die Zahl der Parameter kann man reduzieren, indem man die
kleinstmögliche Zahl als Offset abzieht und erst zur Ausgabe wieder dazu
nimmt. Dann hat man immer einen Bereich von 0 bis x.
Okay, ich verstehe nur nicht in welcher weise das meinen Rechenaufwand reduziert. Ob ich in einem Feld von 3 bis 10 für 8 Schritte durchinkrementiere oder von 0 bis 7 macht aus meiner Sicht keinen Unterschied in der Anzahl der Rechenschritte. Ich habe dann nur den zusätzlichen Aufwand am Ende für die Ausgabe jedes mal noch ein Offset dazuaddieren zu müssen (das sind Anzahl-Felder zusätzliche Additionen). Oder übersehe ich hierbei irgendetwas? Bitte korrigiere mich wenn ich falsch liege.
Brauchst du den explizit alle Ergebnisse oder
genügt die Anzahl möglicher Ergebnisse?
Ich benötige am Ende in jedem Fall alle Ergebnisse in einer XML-Datei.
Zur Vereinfachung wäre es schön wenn ich vorher ausrechnen könnte wie viele es werden aber das ist eher optional da es mir die eigentlich Arbeit nicht erspart.
Also hab ich für Dein Beispiel mit den 4 Feldern mal geschaut wie viele Permutationen möglich sind und das sind 4! = 24. Das scheint doch machbar bis ich ausrechnen wollte wie viele Startwerte es dann geben muss also 282:24 und das ist 11.75 und das scheint mir nicht aufzugehen. Irgendwo ist also bis hier noch ein Denkfehler drin. Dann ist mir aufgefallen das z.B. bei dem Muster 9.1.0.0 eben keine 24 Permutationen möglich sind sondern weniger weil die 0 doppelt vorkommt und ich bei den fertigen Mustern keine Dupletten erzeugen darf. Ich muss alle gültigen Muster finden und darf aber auch keines doppelt nennen. Das bedeutet das ich nach jedem Permutationsdurchgang immer noch alle Dupletten ausfiltern muss, das ist bei 24 möglichen Permutationen für 4 Felder sicher machbar aber wenn es 10 Felder werden und damit 3'628'800 Permutationen wird das Ausfiltern von Dupletten doch sehr aufwendig. Falls es mal 20 Felder werden und damit 2'432'902'008'176'640'000 Permutationen wird das Ausfiltern von Dupletten aber eher unmöglich (ich fürchte ich finde keinen Computer mit ausreichend RAM).
Ich bin mir nicht sicher aber intelligentes Zählen, bei dem direkt von einem gültigen Muster zum nächsten "gezählt" wird, scheint mir doch realistischer als Lösungsansatz.
Daher besser einen Weg der nicht 10000 Mal probiert.
Ach, sag blos. ;)
Ungefähr das war mein Gedanke als ich diesen Thread gestartet hatte. Bei unseren richtigen Aufgaben liegt die Komplexität bei etwa 10^9 bis 10^12 und nicht nur bei 10^4. Eventuell kommt sogar mal eine Aufgabe mit der Komplexität von etwa 10^20 auf mein fertiges Programm zu.
Einen rekursiven Algorithmus möchte ich vermeiden da ich kaum abschätzen
kann wie viele Rekursionsebenen es werden könnten und man da ja
aufpassen muss das der Stack nicht ausgeht.
Das lässt sich sehr gut abschätzen. Wie ich es beschrieben habe, ist die Rekursionstiefe gleich der Anzahl der Felder. Und die ist ja nicht so hoch.
von Jobst Q. schrieb:
Die Zahl der Parameter kann man reduzieren, indem man die
kleinstmögliche Zahl als Offset abzieht und erst zur Ausgabe wieder dazu
nimmt. Dann hat man immer einen Bereich von 0 bis x.
Okay, ich verstehe nur nicht in welcher weise das meinen Rechenaufwand
reduziert. Ob ich in einem Feld von 3 bis 10 für 8 Schritte
durchinkrementiere oder von 0 bis 7 macht aus meiner Sicht keinen
Unterschied in der Anzahl der Rechenschritte. Ich habe dann nur den
zusätzlichen Aufwand am Ende für die Ausgabe jedes mal noch ein Offset
dazuaddieren zu müssen (das sind Anzahl-Felder zusätzliche Additionen).
Oder übersehe ich hierbei irgendetwas? Bitte korrigiere mich wenn ich
falsch liege.
Die kleinste Zahl als Offset brauchst du nur in der Ausgabe. Ansonsten wird alles einfacher, da der Bereich immer mit 0 anfängt und du einen Parameter einsparst. Durch die vielfache Rekursion, die aber nicht tief geht, wird das bedeutsam.
Nicht ganz trivial ist die Ausgabe der gefundenen Kombinationen. Ich würde vorschlagen, das als String an eine Ausgabefunktion zu übergeben. Für 0 bis 9 gehen die Dezimalziffern, für weitere Zahlen kann man sie einfach nach oben erweitern. 10 wäre dann ':', 11 ';', usw.
Als Eingangsparameter käme zu Felder, Quersumme und Bereich noch ein Stringzeiger auf die ersten Felder dazu. Also "62" und Felder=2, Quersumme=2, Bereich = 3, um im obigen Beispiel (Felder=4, Quersumme=10, Bereich = 10) die Kombinationen mit 6 und 2 in den ersten Feldern auszugeben. Damit kann die Ausgabefunktion mit dem String "6202", "6211" und weiteren bedient werden.
Und was ist mit
9,0,1,0
9,0,0,1
8,0,2,0
8,0,0,2
...
Vollständig ist die so generierte Liste jedenfalls nicht.
Das sind Permutationen von 9,1,0,0 und 8,2,0,0.
Das ist mir inzwischen auch klar geworden.
Ich finde es aber umständlich, erst Startwerte zu suchen und auf die dann Permutationsfunktionen loszulassen. Nur eine Funktion rekursiv zu nutzen, scheint mir da doch einfacher. Keep it simple. Komplizierter wird es von allein.
gesehen. Mein Problem ist das die Gesamtanzahl der möglichen Muster
(Größe-Alphabet hoch Anzahl-Felder) im Bereich 10^9 bis 12^12 liegt (und
wir haben hier eine Variante wo die Komplexität für
Brute-Force-Durchzählen bei etwa 10^20 ist, das ist auch für einen
modernen PC mit GHz-CPU zu viel so das wir das bis jetzt noch nichtmal
probiert haben).
Mach mal ein konkretes Beispiel: Symbole von-bis, Anzahl der Stellen und Quersumme.
10^20 sind ungefähr 14 Stellen mit einem 25-er Alphabet. Es hängt extrem von der Quersumme ab, wie viel tatsächliche Kombinationen es gibt. (Worst Case sind hier "mittlere" Werte.)
Vergiss im übrigen das Partitionierungs-Gedöns, und Permutationen. Das ist nice zu wissen, hilft dir hier konkret aber nicht. Alles wo du hinterher Dubletten rausfiltern musst bringt dir auch nichts, weil du dazu alle Lösungen zwischenspeichern müsstest. Du willst einmal, geordnet den kompletten Lösungsraum durchschreiten. Nicht mehr, aber auch nicht weniger.
Einen rekursiven Algorithmus möchte ich vermeiden da ich kaum abschätzen
kann wie viele Rekursionsebenen es werden könnten und man da ja
aufpassen muss das der Stack nicht ausgeht.
Keine Angst, die rekursiven Algorithmen haben nur so viele Ebenen wie du Stellen hast.
Wenn du eine rekursive Lösung hast kann man das jederzeit zu einer iterativen Lösung umbauen. Das ist eine Programmierübung die man eh ein paar mal üben sollte.
Wenn du alle Lösungen haben willst ist es unvermeidbar, den ganzen Baum ein mal komplett durchzugehen.
Wenn du zählen willst, wie viele Lösungen es gibt empfehle ich einen Dynamic-Programming-Ansatz: Du gehst ganz normal rekursiv den Baum durch, aber lässt dir die Anzahl der gefundenen Lösungen als Funktionsergebnis liefern. Zusätzlich speicherst du die Teilergebnisse in einem Cache. Als Key die Anzahl Stellen und die Quersumme, als Value die Zahl der gefundenen Lösungen.
Bei einem Alphabet 2..9 würde da z.B. stehen:
1
2 Stellen, Quersumme 4: 1 Lösung
2
2 Stellen, Quersumme 5: 2 Lösungen
3
2 Stellen, Quersumme 14: 5 Lösungen
4
2 Stellen, Quersumme 15: 4 Lösungen
und natürlich später auch Lösungen für 3 Stellen, 4 Stellen etc.
Wenn du dann in Zukunft bei der Rekursion nochmal absteigen musst kannst du stattdessen den gespeicherten Wert verwenden.
Wenn man an dieser Stelle das Hirn noch etwas weiter verknoten will kommt man drauf, dass man die Rekursion gar nicht braucht und dass man die Ergebnisse von z.B. 3-Stellen aus den 2-Stellen-Ergebnissen berechnen kann. Und dass man die 2-Stellen-Ergebnisse danach nicht mehr braucht.
Das ganze kann man dann mit 2 Arrays und einer 3-fach geschachtelten Schleife ausrechnen (außen aufsteigend Anzahl Stellen, innen Alphabet-Symbole und Quersummen-Werte). Das geht in die Richtung, wo die Partitionierungs-Algorithmen helfen.
Die Zahl der Parameter kann man reduzieren, indem man die
kleinstmögliche Zahl als Offset abzieht und erst zur Ausgabe wieder dazu
nimmt. Dann hat man immer einen Bereich von 0 bis x.
Okay, ich verstehe nur nicht in welcher weise das meinen Rechenaufwand
reduziert. Ob ich in einem Feld von 3 bis 10 für 8 Schritte
durchinkrementiere oder von 0 bis 7 macht aus meiner Sicht keinen
Unterschied in der Anzahl der Rechenschritte.
Angenommen du hast noch 3 Stellen übrig. Dann gibt es folgende Abbruchkriterien:
1
Rest-Quersumme > 3 x 10 // alle verbleibenden Stellen auf max
2
Rest-Quersumme < 3 x 3 // alle verbleibenden Stellen auf min
Das sind 2 Prüfungen. Mit einem 0..7-Alphabet bleibt nur eine Prüfung:
1
Rest-Quersumme > 3 x 7
Das beruht auf der Annahme, dass du die <0-Prüfung in der nächsten Ziffern-Ebene bei der Einschränkung der Auswahlmöglichkeiten ohnehin machen würdest.
Der Zusatzaufwand bei der Ausgabe fällt weniger ins Gewicht, weil du nur "relativ" wenige Lösungen ausgeben musst.
Wie viel das bei dir tatsächlich spart musst du ausprobieren. Ich würde das vorerst mal außer acht lassen. Die Alphabetgrenzen würde ich in globale Konstanten o.ä. speichern, die muss man nicht ständig als Parameter mit durchreichen.
Ok, der Code funktioniert. Aber bitte kein Beispiel daran nehmen.
Keine sprechenden Variablennamen, zu viele Funktionsparameter die unnötig Stack verbrauchen, dann mit einem Buffer die ungeschickteste Möglichkeit zum Zahlen speichern gewählt, dafür dann bei jedem Aufruf nochmal einen Buffer allokieren und kopieren. Mit der potentiell unsicheren Kopierfunktion die sich auf die 0-Terminierung verlässt. Dann noch Pointer Arithmetik.
Die Optimierungen mit der 0-Kette und dem angepassten br bringen wenig, machen den Code dafür größer und kosten Eleganz.
Aber trotzdem Lob (ernst gemeint). An den Details kann man ja noch feilen.
Reine binäre Sachen reichen mir leider nicht, sorry das ich mein
Beispiel zu stark oversimplified hab.
Hm, ich hab's immer noch nicht richtig verstanden. Vielleicht könntest Du die Anforderungen etwas besser darstellen, wenn Du kurz erklären würdest, /wozu/ Du so etwas brauchst, also etwas zum Anwendungsfall erzählst?
Nachdem ich gestern Nacht noch so rumgemeckert habe musste ich heute auch mal eine Lösung bauen.
Haupterkenntnis für mich (wieder mal): ich hab keine Routine mehr in C.
Ich hab mich an Jobst Q.'s Code gehalten, Kommandozeilenparsing und Ausgabe kopiert. Was ich geändert habe ist, dass die Counter-Ausgabe auch bei abgeschaltetem output funktioniert (5. Parameter "o").
Überraschenderweise ist sein Code bei kleinen Quersummen schneller als meiner. Seine Optimierungen bringen da mehr als ich erwartet habe. (Nachfolgende Beispiele nutzen ein Alphabet von 2 bis 25)
Beispiel mit 10 Stellen und kleiner Quersumme (50):
1
$ time ./listqc 10 2 25 50 o
2
211865082 Kombinationen gefunden
3
4
real 0m6.685s
5
user 0m6.683s
6
sys 0m0.000s
7
8
$ time ./listqc-tre 10 2 25 50 o
9
211865082 Kombinationen gefunden
10
11
real 0m19.921s
12
user 0m19.919s
13
sys 0m0.000s
BTW: Der Bereich 2 bis 25 sind 24 mögliche Symbole, hoch 10 Stellen.
24^10 = 6,3 * 10^13.
Bei großen Quersummen fällt sein Code praktisch auf Brute-Force zurück. (7 Stellen, Quersumme 150):
wenn man jetzt die Generierung so gestaltet das diese Matches
Zeitersparnis bringen könnte
das ist das was oben unter dem Stichpunkt "Permutationen" schon ausführlich diskutiert wurde.
Du kannst den rekursiven Algorithmus einfach erweitern, dass der nur (absteigend) sortierte Möglichkeiten durchprobiert.
Als zweite Optimierung könnte der Algorithmus dann früher abbrechen, wenn die verbleibenden Zellen (die dann wegen der Sortierung <= dem aktuellen Wert sind) nicht mehr reichen, um die gewünschte Summe zu erreichen.
Du kannst den rekursiven Algorithmus einfach erweitern, dass der nur
(absteigend) sortierte Möglichkeiten durchprobiert.
Das wäre tatsächlich leicht machbar. Weil da Zahlen mehrfach vorkommen können wird es ziemlich kompliziert, das dann entsprechend zu permutieren.
Wenn ich z.B. die Quersumme 15 in 5 3 3 2 1 1 partitioniert habe, dann muss ich sowohl die doppelte 3 als auch die doppelte 1 beim permutieren berücksichtigen, damit ich keine Dubletten erzeuge.
Wenn es nur um das Zählen der Möglichkeiten könnte man durch die Häufigkeits-Fakultäten teilen. Aber nur zählen geht einfacher, ohne Rekursion, in O(StellenzahlAlphabetgrößeQuersumme).
Besser wäre es vielleicht, gleich nur die Partitionen (mit Häufigkeiten) zu suchen. Die Verteilung auf die einzelnen Stellen macht dann die Permutation.
Blöd ist, dass man bei der Permutationssuche nur Lösungen akzeptieren darf, wo die Stellenzahl genau stimmt. Das ist dann ähnlich wie in den jetzigen Lösungen die passende Quersumme prüfen.
Ich bin mir nicht sicher, wie viel man da tatsächlich spart. Problem sind in beiden Fällen "mittelgroße" Quersummen, weil da die Zahl möglicher Partitionen explodiert.
Es wäre gut wenn der TO tatsächliche Problemgrößen (und den Anwendungsfall) rausrücken könnte.
Das wäre tatsächlich leicht machbar. Weil da Zahlen mehrfach vorkommen
können wird es ziemlich kompliziert
So so, in Mathe nicht aufgepasst ?
Keine Sorge, Grundlagen in Wahrscheinlichkeitsrechnung und Kombinatorik sind noch da, auch wenn das schon ein paar Jährchen her ist.
Der Satz oben ging weiter: "das dann entsprechend zu permutieren."
Wenn du einen Algorithmus hast, der permutiert und dabei mehrfache Zahlen berücksichtigt, ohne dass man sich im Code einen abbricht, also mit einer gewissen Eleganz: immer her damit!
Ich lerne gerne dazu.
Wenn du einen Algorithmus hast, der permutiert und dabei mehrfache
Zahlen berücksichtigt, ohne dass man sich im Code einen abbricht, also
mit einer gewissen Eleganz: immer her damit!
Ich lerne gerne dazu.
Nachdem ich gestern Nacht noch so rumgemeckert habe musste ich heute
auch mal eine Lösung bauen.
Danke Tilo, es hat mich sehr interessiert, wie andere das lösen.
Wie konnte ich nur die Möglichkeit übersehen, die auszugebenden Daten gleich in ein globales Array zu schreiben? Ich gehör ja nicht zu den Leuten, die globale Variablen verdammen, und finde es eher wichtig, die Parameterliste von Funktionen klein zu halten. Das ist etwas, was ich gerne von deinem Programm übernehme.
Überraschenderweise ist sein Code bei kleinen Quersummen schneller als
meiner. Seine Optimierungen bringen da mehr als ich erwartet habe.
Das hat mich auch interessiert. Ich habe daraufhin in beide Programme noch einen Zähler für die Anzahl der Rekursionen eingebaut. Und dabei festgestellt, dass diese bei deinem listqc-tre deutlich höher ist. Da ist vielleicht noch etwas Spielraum für Optimierung. Es liegt vermutlich daran, dass ich den Zahlenbereich verändere, also reduziere, wenn möglich.
Festgestellt habe ich auch, dass bei mir die Zahl der Rekursionen gleich der der gefundenen Kombinationen ist, solange die gewünschte Quersumme kleiner oder gleich von Zahlenbereich + Felder ist. Merkwürdigerweise zeigt die Ausgabe mit r aber, dass nicht jede Rekursion eine Kombination findet.
Bei großen Quersummen fällt sein Code praktisch auf Brute-Force zurück.
(7 Stellen, Quersumme 150):
Auch das hat mir zu denken gegeben. Meine Lösung ist, die Reihenfolge bei der größeren Hälfte umzudrehen. War aber nicht ganz einfach und auch jetzt braucht es abwärts ein paar Rekursionen mehr als aufwärts.
Bei den Zeitmessungen habe ich auch festgestellt, dass die Ausgabe mit printf ein Vielfaches der Zeit des Findens beansprucht, zB das 30fache. Daraufhin habe ich mich um eine schnellere Ausgabe bemüht, mit direkter Stringprogrammierung und puts(). Um das zu vergleichen, kann ich die alte Methode mit Parameter s (für slow) erzwingen.
Hier die Vergleichstests mit den Parametern, die du auch verwendet hast. Auf einem Raspi Zero, wodurch Zeitunterschiede deutlicher werden als auf einem PC.
Obwohl das erste Ergebnisbeispiel falsch ist, ist das wohl eine Lösung.
Natürlich wird die Eleganz dich nicht befriedigen.
Man muss jedenfalls solche Algorithmen nicht neu erfinden, die gibt es
fertig.
Was nützt ein fertiger Algorithmus, wenn man doch einen weiteren Algorithmus erfinden muss, um diesen richtig zu füttern. Dann doch lieber nur einen Algorithmus aus einem Guss.
Und dabei
festgestellt, dass diese bei deinem listqc-tre deutlich höher ist. Da
ist vielleicht noch etwas Spielraum für Optimierung. Es liegt vermutlich
daran, dass ich den Zahlenbereich verändere, also reduziere, wenn
möglich.
Der Faktor ist knapp über 24 - der Anzahl der Möglichkeiten pro Stelle. Ich hatte am Montag zeitweise auch einen zweiten Zähler eingebaut und kam auf den Faktor knapp über 10, als ich mit einem 10er-Alphabet getestet habe.
Der Grund ist, dass ich in der letzten Rekursionsstufe, wenn mit dem verbleibenden Quersummerest völlig klar ist, was die letzte Stelle sein muss, ich in der Schleife trotzdem alle möglichen Werte durchgehe und noch einmal in die Rekursion gehe.
Du hast in diesem Fall immerhin die obere Schranke abgedeckt, indem du die br-Variable entsprechend verkleinert hast.
Ich habe auch daran gedacht das zu machen indem die Schleife nur bis min(restquersumme, max_val) geht. Für die untere Grenze der Schleife ist mir leider nichts eingefallen.
Ich habe mich dann dagegen entschieden. Der Code würde komplizierter und die zusätzliche Abfrage müsste auch in den oberen Rekursionsstufen ausgeführt werden, wo sie wenig bringt. Und ich zahle nur einen konstanten Faktor dafür, das war mir egal.
Am effizientesten wäre wohl, die Rekursion immer in der vorletzten Stufe abzubrechen und die letzte Ziffer zu berechnen.
Wenn man die Sonderbehandlung weiterspinnt könnte man das prinzipiell auch für mehr als eine Stelle machen: bei gegebener Restquersumme gibt es ja immer die gleichen möglichen Endzifferfolgen, die könnte man Zwischenspeichern. CPU gegen Speicher.
Was nützt ein fertiger Algorithmus, wenn man doch einen weiteren
Algorithmus erfinden muss, um diesen richtig zu füttern.
Weils die halbe Arbeit ist
Dann doch
lieber nur einen Algorithmus aus einem Guss.
Divide and Conquer ist nicht dein Ding.
jaja.
Wenn es ein Alphabet mit a unterschiedlichen Möglichkeiten pro Ziffer gibt und insgesamt d Stellen belegt werden sollen, dann spart die Suche nach Partitionen (d.h. absteigender Ziffernfolgen) anstelle aller gültigen Ziffernfolgen ganz grob den Faktor (1/2)^d ein. Dafür müssen dann für jede gefundene Lösung die Permutationen gesucht werden, was einen Faktor O(d^2) kostet.
Ob Partitionen+Permutation wirklich "die halbe Arbeit" gegenüber der deutlich einfacheren Tiefensuche ist, hängt erheblich von den Parametern der Aufgabenstellung ab.
Wenn wegen der Quersumme nur wenige Lösungen gefunden werden und/oder nur wenige Stellen besetzt werden müssen, kann das vorteilhaft sein.
Andererseits scheinen die gezeigten Lösungen dem Problem des TO angemessen leistungsfähig zu sein.
Mich würde allerdings schon interessieren, ob du den von dir vorgeschlagenen Weg implementiert bekommen würdest und wie verständlich der Code dann ist.
Du hast immerhin den Vorteil, gegen mehrere funktionierende Referenzimplementierungen testen zu können.
Ich habe daraufhin in beide Programme
noch einen Zähler für die Anzahl der Rekursionen eingebaut. Und dabei
festgestellt, dass diese bei deinem listqc-tre deutlich höher ist. Da
ist vielleicht noch etwas Spielraum für Optimierung.
Danke für den Ansporn darüber nachzudenken!
Durch umsortieren und weglassen konnte ich noch eine Größenordnung rausholen. (Ich musste die Aufgabe schwieriger machen weil ich keinen PiZero übrig habe.)
1
Parameter Felder:8 Min:2 Max:25 Quersumme:75
2
----------
3
./listqc 8 2 25 75 o
4
563853888 Kombinationen gefunden
5
6
real 0m33.925s
7
user 0m33.923s
8
sys 0m0.000s
9
----------
10
./listqc2 8 2 25 75 o
11
563853888 Kombinationen mit 595752418 Rekursionen gefunden
12
13
real 0m11.433s
14
user 0m11.431s
15
sys 0m0.000s
16
----------
17
./listqc-tre 8 2 25 75 o
18
563853888 Kombinationen mit 14983409377 Rekursionen gefunden
19
20
real 0m44.820s
21
user 0m44.817s
22
sys 0m0.000s
23
----------
24
./listqc-tre2 8 2 25 75 o
25
563853888 Kombinationen mit 1450916065 Rekursionen gefunden
26
27
real 0m5.048s
28
user 0m5.046s
29
sys 0m0.000s
Bei so Optimierungssachen finde ich es immer wieder beeindruckend, wie wichtig kleine Details sind, die man im fertigen Code gar nicht mehr sieht.
Ich fand das bei projecteuler manchmal so krass, wenn ich nach 3 Tagen mit riesigem Aufwand das Ergebnis geradeso rausbekommen habe, und im Forum postet dann jemand einen 5-Zeiler der mehrere Größenordnungen schneller ist.
Mit den neueren Aufgaben dort kann ich leider nicht so viel anfangen. Die sind mir zu mühsam, bei vielen habe ich nicht mal den Hauch einer Idee.
Bei so Optimierungssachen finde ich es immer wieder beeindruckend, wie
wichtig kleine Details sind, die man im fertigen Code gar nicht mehr
sieht.
Ich muss zugeben, dass dein Algorithmus trotz mehr Rekursionen schneller ist, vor allem bei vielen Kombinationen. Vermutlich liegt es doch daran, dass deiner nur 2 Parameter hat und meiner 3.
Aber Optimierungsbedarf hat dein Programm bei der Ausgabe. Die printf-Funktion ist eben ziemlich komplex und der Aufruf für jede Zahl bremst gewaltig.
Hier die Vergleiche mit Ausgabe nach /dev/null, dies mal auf einem schnelleren Rechner:
root@jq600l:/miras/entwick/listqc# time ./listqc2 8 2 25 75 > /dev/null
563853888 Kombinationen mit 595752418 Rekursionen gefunden
real 1m34,071s
user 1m33,338s
sys 0m0,721s
root@jq600l:/miras/entwick/listqc# time ./listqc-tre2 8 2 25 75 > /dev/null
563853888 Kombinationen mit 1450916065 Rekursionen gefunden
real 6m37,411s
user 6m36,493s
sys 0m0,876s
Bei 563 Millionen Ergebnissen ist das schon eine kleine Kaffeepause Unterschied.
Ich fand das bei projecteuler manchmal so krass, wenn ich nach 3 Tagen
mit riesigem Aufwand das Ergebnis geradeso rausbekommen habe, und im
Forum postet dann jemand einen 5-Zeiler der mehrere Größenordnungen
schneller ist.
Wenn ich irgendwann mal wieder mehr Zeit habe, könnte es mich auch interessieren. Bei dieser Aufgabe hier hat es mich einfach gepackt, praktische Erfahrungen zu machen, statt nur herum zu theoretisieren.
Aber Optimierungsbedarf hat dein Programm bei der Ausgabe.
:-)
Auf jeden Fall. Ich habe die Ausgabe nur genutzt um das Ergebnis zu diffen, die Performance habe ich nicht mal getestet.
Yalus' Version sieht da ziemlich optimal aus.
Auch sein pruning spart nochmal einen Faktor 2 bis 3 an Rekursionsaufrufen.
Ich glaube nicht, dass die Tiefensuche jetzt noch weiter verbessert werden kann.
