Hallo,
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:
1.1.2.2 ; 1.2.1.2 ; 1.2.2.1 ; 2.1.1.2 ; 2.1.2.1 ; 2.2.1.1
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.
Hat hier irgendjemand eine Idee?
Grüße Erik
Wie groß ist dein Alphabet, d.h. welche Ziffern lässt du zu?
In deinen Beispielen oben gibt es nur die Ziffern 1 und 2, und immer
jeweils 2 davon. Diese Kombinationen lassen sich einfach enumerieren:
1. Schritt: Position der ersten 2 festlegen (erste bis dritte Stelle, 3
Möglichkeiten)
2. Schritt: Position der zweiten 2 festlegen (nachfolgende bis letzte
Stelle, 3 bis eine Möglichkeit)
> Wie groß ist dein Alphabet, d.h. welche Ziffern lässt du zu?
In meinem realem Problem ist das nicht fest definiert, ich benötige
einen generischen Algorithmus der mit den 4 Parametern:
- Anzahl Felder
- gewünsche Summe
- 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)
Reine binäre Sachen reichen mir leider nicht, sorry das ich mein
Beispiel zu stark oversimplified hab.
Grüße
Erik
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:
1. 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.
flip schrieb:> meinst du sowas in der art?
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.
Nennt sich "Partitionierung" und hat eine ganz interessante Theorie,
siehe etwa https://de.wikipedia.org/wiki/Partitionsfunktion und Freunde.
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.
Hier in C hingeschlunzt:
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.
Erik schrieb:> 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
7,3,0,0
7,2,1,0
7,1,1,1
6,4,0,0
6,3,1,0
6,2,2,0
6,2,1,1
5,5,0,0
usw. bis
3,3,3,1
3,3,2,2
Michael B. schrieb:> Du willst permutieren.
Für dieses einfache Beispiel schon, im allgemeinen trifft dies aber
nicht zu:
Angenommen, wir wollen 6 zerlegen in 2 Summanden aus { 1, 2, 3, 4, 5, 6
}. Mögliche Zerlegungen sind dann:
1 + 5, 2 + 4, 3 + 3, 4 + 2 und 5 + 1
und i.d.R sind dies nicht Permutationen voneinander.
Erik schrieb:> - Anzahl Felder> - gewünsche Summe> - 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.
Johann L. schrieb:> Für dieses einfache Beispiel schon, im allgemeinen trifft dies aber> nicht zu:
Was meinst du, warum ich das zweite Beispiel mit den möglichen
Vorbelegungen des fann zu permutierenden Arrays schon beschrieben hatte
?
Damit auch du es liest !
Michael B. schrieb:> Erik schrieb:>> 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.
Hallo,
Danke für die zahlreichen Antworten!
von Johann L. schrieb:
> Nennt sich "Partitionierung" und hat eine ganz interessante Theorie,> siehe etwa https://de.wikipedia.org/wiki/Partitionsfunktion und Freunde.
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.
Grüße Erik
Johann L. schrieb:> 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.
Jobst Q. schrieb:> 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.
Daher muss er permutieren, nicht zählen.
Weisst du mit dem Begriff Permutation nichts anzufangen ?
Die Startwerte habe ich genannt, deren Erzeugung ist trivial.
Erik schrieb:> aber ich hatte die Vermutung das wenn ich eine Zahl um eins erhöhe da> ich dann eine andere Zahl um eins verringern muss
Ja.
Damit machst du dich bzw. deinen uC wegen Überarbeitung tot.
Daher besser einen Weg der nicht 10000 Mal probiert.
Michael B. schrieb:> Daher muss er permutieren, nicht zählen.
Okay, hab ich verstanden und klingt logisch.
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.
Bitte korrigiere mich wenn ich falsch liege.
Michael B. schrieb:> 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.
Grüße Erik
Erik schrieb:> 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.
Michael B. schrieb:> Jobst Q. schrieb:>> 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.
Erik schrieb:> 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.
Erik schrieb:> 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.
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.
Erik schrieb:> 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?
Also ich sehe da keinen algorithmus..
Das ist doch nur Felder lesen, alles skippen wenn die Summe zu groß wird
und wenn die Summe erreicht ist und das letzte Feld fertig ist, ein
Match.
For Feld in Felder
Feldcnt++;
If(Feld<max&&Feld>min)tempsumme+=Feld
If(tempsumme>summe)Return False
If(Feldcnt==Felder)
If(tempsumme==Summe)Return true Else Return False
...
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):
Das interessante ist ja auch, hast du einen Match, hast du ja mehrere
Matches.. dann halt nur die gleichen Zahlen anders sortiert.
wenn du 1,1,1,2 gefunden hast weisst du das 1,1,2,1 und 1,2,1,1 und
2,1,1,1 auch mit Summe 6 matchen werden.
wenn man jetzt die Generierung so gestaltet das diese Matches
Zeitersparnis bringen könnte das bei großen Sachen noch schneller
werden.
TotoMitHarry schrieb:> 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.
Εrnst B. schrieb:> 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(Stellenzahl*Alphabetgröße*Quersumme).
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.
Michael B. schrieb:> Tilo R. schrieb:>> 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.
Tilo R. schrieb:> 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.
pi@raspips:~ $ ./test.sh 7 2 25 150
Parameter Felder:7 Min:2 Max:25 Quersumme:150
----------
./listqc2 7 2 25 150 o
736232 Kombinationen mit 906052 Rekursionen gefunden
real 0m0,806s
user 0m0,709s
sys 0m0,022s
----------
./listqc-tre 7 2 25 150 o
736232 Kombinationen mit 21745753 Rekursionen gefunden
real 0m2,020s
user 0m1,814s
sys 0m0,013s
----------
./listqc2 7 2 25 150 > /dev/null
736232 Kombinationen mit 906052 Rekursionen gefunden
real 0m2,108s
user 0m1,835s
sys 0m0,075s
----------
./listqc2 7 2 25 150 s > /dev/null
736232 Kombinationen mit 906052 Rekursionen gefunden
real 0m12,188s
user 0m9,789s
sys 0m0,221s
----------
./listqc-tre 7 2 25 150 > /dev/null
736232 Kombinationen mit 21745753 Rekursionen gefunden
real 0m12,329s
user 0m10,132s
sys 0m0,226s
Michael B. schrieb:> 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.
Jobst Q. schrieb:> 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.
Michael B. schrieb:> Jobst Q. schrieb:>> 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 machs doch, dann können wir vergleichen.
Jobst Q. schrieb:> 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.
Jobst Q. schrieb:>> 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.
Das ist ein cooler Trick!
Michael B. schrieb:> Jobst Q. schrieb:>> 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.
Jobst Q. schrieb:> 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.
Tilo R. schrieb:> 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.
Jobst Q. schrieb:> 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.
Erik schrieb:> In meinem realem Problem ist das nicht fest definiert, ich benötige> einen generischen Algorithmus der mit den 4 Parametern:> - Anzahl Felder> - gewünsche Summe> - 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)
Nennt man eine Reihe.
Aber da du mit Mathe nichts im Sinn hast, kannst du das auch nicht
lösen.
Yalu X. schrieb:> Hier sind die Zeiten im Vergleich, gemessen auf einem i5-6267U mit 2,90> GHz.
Auch interessant, hier mal mit einem 2,4Ghz ARM (RK3588).
Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.
Wichtige Regeln - erst lesen, dann posten!
Groß- und Kleinschreibung verwenden
Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang
Announcement: there is an English version of this forum on 
Thread beobachten
Seitenaufteilung abschalten