Hallo,
ich habe wieder einmal ein Problem, dass ich zum einen sehr interessant finde, zum anderen mir aber auch schlaflose Nächte bereitet hat.
Bekannt wurde es unter dem Namen "Des chiffres et des lettres" aus einer Spielshow des französischen Fernsehens. Mittlerweile ist es auch in anderen Ländern populär geworden. In den USA gibt es z.B. T-Shirts mit der Aufschrift


Die Aufgabe ist, aus einer Menge gegebener Zahlen durch schrittweise Addition, Subtraktion, Multiplikation und Division eine Zielzahl zu ermitteln. Dabei darf und muss jede gegebene Zahl und jedes Zwischenergebnis genau einmal verwendet werden!
Beispiel: Aus den Zahlen 1 bis 6 ist die 278 zu konstruieren
4 · 5 = 20
3 + 20 = 23
23 · 6 = 138
1 + 138 = 139
139 · 2 = 278
Als einzelne Gleichung ergibt sich damit ((3 + 4 · 5) · 6 + 1) · 2 = 278.
Im Allgemeinen existieren entweder mehrere Lösungen oder aber gar keine. Aus den Zahlen n = 4, 5, 6, 7, 8 kann z = 29 zum Beispiel nicht konstruiert werden.

Meine Umsetzung als Programm nutzt vier Routinen, die sich gegenseitig rekursiv aufrufen. Elegant ist das nicht und vor allem für mehrere Ausgangszahlen wird es ziemlich langsam.
Schön wäre es, wenn jemand von Euch eine bessere Idee hätte.

Im Programm werden 4 bis 8 Ausgangszahlen betrachtet. Die möglichen Operationen Addition, ... können ausgewählt werden.
Mit dem Schalter "Problem lösen" werden alle möglichen Lösungen gesucht. Über den Schalter "Folge berechnen" wird beginnend bei der eingegebenen Zielzahl jeweils 1 Lösung ermittelt, die Zielzahl erhöht, erneut gesucht usw. bis eine Zielzahl ohne Lösung gefunden wird.

Beste Grüße
Mathematiker

Rev 1: Algorithmus korrigiert und Folgenberechnung vorerst entfernt.
Rev 2: Ein weiterer Fehler ist korrigiert. Es wurden nicht alle gefundenen Lösungen ausgegeben. Jetzt müsste es korrekt sein.
Rev 3: Die Folgenberechnung ist wieder möglich.
Rev 4: Die berechneten Ergebnisse können in einer Textdatei gespeichert werden.
Rev 5: Die Tests und damit auch die Rechenzeit sind deutlich auf etwa 25% gekürzt.
Rev 6: Es werden nur noch Ergebnisse angezeigt, die nach dem Kommutativgesetz voneinander verschieden sind.
Rev 7: Weitere deutliche Beschleunigung der Berechnung durch Reduktion der Rekursionsaufrufe.
Rev 8: Mit einer 3.Berechnung können nun alle möglichen Zielzahlen in einem festgelegten Bereich ermittelt werden. Besonders schnell!
Rev 9: "Folge berechnen" ist entfernt, da die Routine "Ziele suchen" die gleiche Aufgabe wesentlich schneller absolviert. Weitere Änderungen verkürzen die Rechenzeiten noch einmal.
Rev 10: Weitere Änderungen, vor allem der Tests.
Rev 11: Fehlerhafte Version 10 korrigiert.
Rev 12: Beim Aufruf der rekursiven Methoden wird kein Feld mehr direkt übergeben, d.h. wieder etwas schneller.

Ich würds auch per Bruteforce lösen:

Die Zahlen permutieren und bei jedem Perumationsschritt alle Kombinationen für die Rechenopeartionen ermitteln - den Wert evaluieren und zwischenspeichern.
Letzendlich würde ich dann diejenigen ausgeben, die gleich "Zielzahl" sind.

Hmm... es ist aber ein interessantes Problem.
Gibts eig. schon (ordentlich) mathematische Ansätze zu diesem Problem?

Hallo,
im Endeffekt läuft es bei mir ja auch mit Bruteforce. Und das dauert eben, gerade wenn es dann 7 oder 8 Ausgangszahlen sind.
Als Beispiel: Die Berechnung der Zerlegungen von 1 bis 18920 mit den Ausgangszahlen 2, 3, 5, 7, 11, 13, 17 und 19 benötigte auf meinem 2,6 GHz-PC über 70 Stunden.
In englischsprachigen Ländern wurde das Problem unter dem Namen "Letters and Numbers" (oder umgedreht) bekannt, zuerst in Australien, später in den USA.

Mr_Emre_D hat folgendes geschrieben :

Gibts eig. schon (ordentlich) mathematische Ansätze zu diesem Problem?

Trotz ausführlicher Netzsuche habe ich noch nichts gefunden. Leider.

Beste Grüße
Mathematiker

Kurze Regelfrage... was ist mit Nicht-Ganzen und negativen Zwischenergebnissen? Und Zwischenergebnissen, die gleich Zahlen sind die schon im Pool sind (ist [2,3,6]->12 als 2*3,6+6,12 möglich)?
Und dann wäre da ja noch das Problem der vielfachen äquivalenten Lösungen. Da waren wir ja schonmal beim Gleichungen vereinfachen

Ansonsten: würde das stimmen? Die Rechnungen sind jeweils von rechts nach links zu lesen, das war grad einfacher programmiert Ist ein dummes Bruteforce, also auch keine neue Idee.


PS: mit Abbruch nach erstem Fund:

Hallo Martok,

Martok hat folgendes geschrieben :

Kurze Regelfrage... was ist mit Nicht-Ganzen und negativen Zwischenergebnissen? Und Zwischenergebnissen, die gleich Zahlen sind die schon im Pool sind (ist [2,3,6]->12 als 2*3,6+6,12 möglich)?

Negative Zwischenergebnisse sind zugelassen, gebrochene aber nicht, d.h. die Division muss "aufgehen". Tritt ein Zwischenergebnis auf, dass evtl. einer der Zahlen entspricht, so wird trotzdem mit diesem einfach weitergerechnet.

Martok hat folgendes geschrieben :

Und dann wäre da ja noch das Problem der vielfachen äquivalenten Lösungen. Da waren wir ja schonmal beim Gleichungen vereinfachen

Äquivalente Lösungen habe ich im Moment als weitere gezählt. Das Problem mit der Vereinfachung verfolgt uns scheinbar immer wieder.
Ich hatte schon einmal die Idee aus dem Term einen UPN-Term zu machen. Vielleicht könnte man dann einfacher äquivalente ausfiltern. Allerdings schrecke ich davor noch zurück. Ich mag UPN einfach nicht.

Für Dein Beispel pool is 1,2,3,4 / target 9 hat Du (ohne Division) 28 Lösungen, ich nur 20, also sind mir wohl ein paar abhanden gekommen.
Für 1,2,3,4,5,6 und target 278 braucht mein Programm nur rund 1 Sekunde für das Testen aller Möglichkeiten.

Beste Grüße
Mathematiker

Nachtrag: Ich habe gerade gesehen, dass mir alle Lösungen fehlen, die mit einer Subtraktion mit einem negativen Ergebnis beginnen.
Nachtrag 2: Ich habe die Lösungen doch, nur in der Form (4-1)+(2*3). Einige bei Dir verschiedene, sind bei mir ausgeblendet.
Nachtrag 3: Mein Algorithmus hat einen entscheidenden Fehler. Es werden nicht alle Möglichkeiten getestet. Sehr ärgerlich.
Nachtrag 4: Ich habe (hoffe ich) den Fehler im Algorithmus entfernt. Vorerst gibt's auch keine Folgenberechnung mehr. Die machte den Quelltext unübersichtlich.

Mathematiker hat folgendes geschrieben :

Negative Zwischenergebnisse sind zugelassen, gebrochene aber nicht, d.h. die Division muss "aufgehen".

Damit kann man die Frage in dem Bild in Deinem ersten Post ganz klar mit nein beantworten. Jedenfalls in dem von Dir erlaubten Zahlenraum.
(Ansonsten ginge 8/(3-5/2)=16)

Für einen Algorithmus müsste man wohl erst einmal die Existenz einer Lösung nachweisen bzw. voraussetzen können. Allein das ist wohl schon schwierig genug.

Hallo Marc.,

Marc. hat folgendes geschrieben :

Damit kann man die Frage in dem Bild in Deinem ersten Post ganz klar mit nein beantworten.

Wow, ich habe bisher noch nicht geprüft, ob dass auf dem T-Shirt möglich ist.
Du hast vollkommen recht. In der Original-Spielshow musste die Division aber aufgehen. Obwohl es mit meinen Kenntnissen der französischen Sprache nicht so gut aussieht, habe ich mir auf "TV 5" die Sendung ab und an mal angesehen.

Lässt man gebrochene Zwischenergebnisse zu, heißt das für das Programm, dass der Algorithmus deutlich schwerer wird.

In der Revision 2 habe ich einen blöden Fehler beseitigt. Es wurden nicht alle gefundenen Lösungen ausgegeben. Jetzt müsste es korrekt sein.

Beste Grüße
Mathematiker

Nachtrag: Das T-Shirt ist wohl für richtige Nerds. Ein "normaler" US-Amerikaner wird die Aufgabenstellung gar nicht verstehen, geschweige denn eine Lösung finden.
Lässt man sogar Kommas zu, geht auch: 8 * (3 - (,5 * 2)) = 16.
Interessant ist Nerds-Gifts.

Nachtrag 2: In der Revision 3 ist die Folgenberechnung wieder möglich.

Also, bei 6 Zahlen gibt es oft schon 3000 - mehr als 6000 Lösungen. Das ist schon gewaltig. Obwohl wahrscheinlich die rel. Lösungshäufigkeit nicht ansteigt. Aber mit Permutationen hab ich das nicht so.

Hallo Tranx,

Tranx hat folgendes geschrieben :

Also, bei 6 Zahlen gibt es oft schon 3000 - mehr als 6000 Lösungen. Das ist schon gewaltig.

Das finde ich auch überraschend.
Interessanter finde ich aber die Berechnung von mindestens einer Lösung für aufsteigende Zielwerte (Folge berechnen). Ich habe gerade für die Ausgangszahlen 2, 3, 5, 7, 11, 13, 17 für alle Zahlen von 1 bis 1800 wenigstens eine Darstellung ermitteln lassen. Knapp 25 Minuten Rechenzeit sind ziemlich viel.

Beste Grüße
Mathematiker

Das ist natürlich der Vorteil von meiner Lösung. Da werden alle möglichen Ergebnisse berechnet, die sich mit dem Pool erreichen lassen, das wird dann nur nach dem target gesiebt. Kann man natürlich dann andersrum rangehen und von dieser Liste wiederum min/max nehmen, dann weißt du, dass du alle erzeugbaren Werte dazwischen kennst

Hallo Martok,

Martok hat folgendes geschrieben :

Das ist natürlich der Vorteil von meiner Lösung. Da werden alle möglichen Ergebnisse berechnet, die sich mit dem Pool erreichen lassen, das wird dann nur nach dem target gesiebt.

Klingt sehr gut. Die Lösung würde mich sehr interessieren.

Beste Grüße
Mathematiker

Wenn "Brute Force" und Permutierung Grundlagen der Lösung sind, ist dann ein möglichst schneller Permutationsalgorithmus vorteilhaft? M.E. ja!

Hallo Delphi-Laie,

Delphi-Laie hat folgendes geschrieben :

... ist dann ein möglichst schneller Permutationsalgorithmus vorteilhaft?

Du hast schon recht und wenn ich es richtig verstanden habe, nutzt Martok auch alle Permutationen der Zahlen, Operationen und Klammermöglichkeiten.

Dies sind bei n Zahlen und alle Operationen ziemlich viele Möglichkeiten. Nach meiner Abschätzung gleich n! (n-1)^4 C(n), wobei C(n) = (2n)! / ((n+1)! n!) die n.te Catalansche Zahl ist, welche die Anzahl der Klammermöglichkeiten eines Berechnungsterms mit n Zahlen angibt.
n! sind die Permutationen der n Zahlen und (n-1)^4 die Anzahl der Operationsmöglichkeiten zwischen den Zahlen.
Für 6 Zahlen sind das 59,4 Millionen, für 7 Zahlen schon 2,8 Milliarden und für 8 Zahlen 138 Milliarden Möglichkeiten; bei einer einzigen Suche!

Den größten Zeitbedarf hat in meinem Programm die Überprüfung, ob das gewünschte Resultat erzeugt wird. Und das braucht seine Zeit. Deshalb hoffe ich ja, dass jemand eine vielleicht bessere Idee hat.

Beste Grüße
Mathematiker

Hallo,

Warum nicht einen UPN- Parser.
Ein Stack mit den vorhandenen n Zahlen und einen mit den n-1 möglichen operatoren , die immer auf zwei Elemente wirken.
Den Zahlen Stack mit allen Permutationen der n Zahlen füttern und die Operatoren mit den Zahlen 1..4 symbolisch für +,-,*,/
Wenn man einen Operator ändert, hat man ja immer noch das Ergbebnis der Berechnung der vorherigen Zahlen auf dem Stack.
Zu früh am Tag, später mehr

Gruß Horst

Ein Problem ist noch zu bedenken:

Neben der Kombinatorik der Operatoren gibt es ja noch die der Klammern:

(5 * 4) + 6 ist nicht gleich 5 *(4 + 6). Die Operatoren jedoch sind in der gleichen Reihenfolge.

Hallo Tranx,

Tranx hat folgendes geschrieben :

Neben der Kombinatorik der Operatoren gibt es ja noch die der Klammern: ...

Aus diesem Grund werden die zu untersuchenden Möglichkeiten so schnell groß.

Tranx hat folgendes geschrieben :

(5 * 4) + 6 ist nicht gleich 5 *(4 + 6).

Bei UPN wird der erste Term zu 5 4 * 6 +, der zweite zu 5 4 6 + *, d.h. sie sind unterscheidbar.

Vor Jahren habe ich mir einmal die Mühe gemacht, eine Routine zu schreiben die AOS-Terme in UPN transformiert. Die Umkehrung habe ich leider nicht. Kennt jemand von Euch für die Transformation von UPN nach AOS eine Quelle? Hier in der EE bin ich noch nicht fündig geworden.

Beste Grüße
Mathematiker

Hallo,

ich habe die Vorstellung das ich alle z.B 6 Zahlen auf den Stack schiebe und anschließend die 5 Operatoren.
Ich hoffe, alle Berechnungsmöglichkeiten durch die Permutation der Zahlen zu erfassen.
(5 * 4) + 6 = UPN 5 4 * 6 + = UPN 6 5 4 * +


Bei 6 Zahlen und 4 Operatoren pro Berechnung habe ich folgende Kombinationen an Berechnungen
4( Berechung 1) +4*4( Berechung 2) +4*4*4 +4*4*4*4 +4*4*4*4*4 = 1364 bei einer Zahlenkombination.
Da 1+k+k²+k³+...k^n = ( k^(n+1)-1)/(k-1) ist ergibt sich hier auch so
(4^6-1)/(4-1) -1 = 1364
Jetzt gibt es 720 Permutationen der Zahl1..Zahl6 so sind es dann 982080 Berechungen an der Zahl.

Zitat:

Für 6 Zahlen sind das 59,4 Millionen

Welche Berechnung wird denn nicht erfasst?

Gruß Horst

Die Sache ist sogar noch einfacher, da du Operatoren mehrfach verwenden darfst. Da brauchst du nur die Zahlen auf einen Stack schieben, und diesen in einer Art Tiefensuche für jede Operation einmal verwürfeln. Ich bin mir relativ sicher, dass mein Code dazu mindestens doppelt so viel tut wie er muss (das könnte auch quadratisch sein), aber dafür ist er dank JS-Array Comprehensions sehr einfach

Hallo Horst_H,

Horst_H hat folgendes geschrieben :

Jetzt gibt es 720 Permutationen der Zahl1..Zahl6 so sind es dann 982080 Berechungen an der Zahl. Zitat: Für 6 Zahlen sind das 59,4 Millionen Welche Berechnung wird denn nicht erfasst?

Nach Deiner Idee werden, wenn ich es richtig verstehe, für vier Operanden alle Möglichkeiten

berechnet. Dabei fehlt aber u.a. die Variante (a • b)•(c • d).
Wie ich schon weiter oben geschrieben habe, beschreibt die Catalansche Zahl C(n) (de.wikipedia.org/wiki/Catalan-Zahl) die Anzahl der Klammermöglichkeiten/Paarbildungen. Für n = 4 Elemente werden es C(n-1) = C(3) = 5. Diese sind:

Oben hatte ich den Fehler C(n) gemacht; es sind aber "nur" C(n-1).
Bei 4 Operationen kann jede auch mehrfach auftreten, d.h. die Operationen permutieren nicht nur, sondern bilden eine Variation mit Wiederholung von 4 (Operationen) zu n-1 Verknüpfungen, d.h. = 4^(n-1). Mein 2.Fehler oben.
Mit den Permutationen der n gegebenen Zahlen wird damit insgesamt
n! 4^(n-1) C(n-1) = n! 4^(n-1) (2(n-1))! / (n! (n-1)!) = 4^(n-1) (2n-2)! / (n-1)!
Für n = 6, 7, 8 werden es insgesamt 30,9 Millionen , 2,7 Milliarden und 283 Mlliarden Möglichkeiten. Für zunehmende n wachsen die Möglichkeiten also noch stärker an.
Bei meiner ersten Berechnung hatte ich leider 2 Fehler. Entschuldigung.

Hallo Martok,

Martok hat folgendes geschrieben :

Die Sache ist sogar noch einfacher, da du Operatoren mehrfach verwenden darfst. Da brauchst du nur die Zahlen auf einen Stack schieben, und diesen in einer Art Tiefensuche für jede Operation einmal verwürfeln.

Diese Idee klingt wirklich gut.

Nebenbei: Bei meinem eigenen Versuch rufe ich die oben berechnete Zahl die Methoden für Addition, Subtraktion, usw. rekursiv auf und übergebe ein Feld von Zahlen.
Dies erschien mir sehr aufwendig. Deshalb habe ich es mit genau einem zweidimensionalen Feld versucht, bei dem im 2.Index die Rekursionstiefe gespeichert wird. Leider dauert das noch länger.

Beste Grüße
Mathematiker

Nachtrag: Ich habe in meiner Lösung die Aufrufe der Routinen gezählt. Für 6 Zahlen waren es einmal 112 Millionen, ein zweites Mal 152 Millionen. Hoffentlich habe ich mich schon wieder verrechnet. Ob am Programm etwas nicht stimmt , muss ich testen. Die unterschiedlichen Werte können aber dadurch entstehen, dass die Aufrufe fehlen, die wegen nicht "aufgehenden" Divisionen entfallen.

Nachtrag 2: Die überzähligen Tests haben mich beschäftigt. Und siehe da, im Programm waren zwei unnötige Tests je Routine. Damit konnte ich die Anzahl der Tests und somit auch die Rechenzeit deutlich auf etwa 25% kürzen.

Mathematiker hat folgendes geschrieben :

Den größten Zeitbedarf hat in meinem Programm die Überprüfung, ob das gewünschte Resultat erzeugt wird. Und das braucht seine Zeit. Deshalb hoffe ich ja, dass jemand eine vielleicht bessere Idee hat.

Warum nicht einfach vom Probeergebnis das gewünschte subtrahieren (oder umgekehrt) und auf 0 vergleichen?