Testen der Äquivalenz mathematischer Ausdrücke in Python

8

Ich habe zwei Strings in Python,

%Vor%

und

%Vor%

das sind äquivalente Funktionen der ungeordneten Menge (A, C) und der ungeordneten Menge (B). m und s geben Einheiten an, die zwischen denselben, aber nicht mit einer anderen Einheit ausgetauscht werden können.

Bis jetzt mache ich Permutationen von A, B und C und teste sie mit dem Operator eval und SymPy ==. Dies hat mehrere Nachteile:

  • Für kompliziertere Ausdrücke muss ich eine große Anzahl von Permutationen erzeugen (in meinem Fall 8 verschachtelte für Schleifen)
  • Ich muss A, B, C als Symbole definieren, was nicht optimal ist, wenn ich nicht weiß, welche Parameter ich haben werde (also muss ich alle generieren - und das ist schrecklich ineffizient und bringt meinen variablen Namespace durcheinander )

Gibt es einen pythonischen Weg, um auf diese Art von Äquivalenz zu testen? Es sollte ein beliebiger Ausdruck funktionieren.

    
Michael Schubert 27.05.2011, 16:10
quelle

5 Antworten

3

Hier ist ein vereinfachter Ansatz basierend auf meiner vorherigen Antwort.

Die Idee ist, dass, wenn zwei Ausdrücke unter Permutationen äquivalent sind, die Permutation, die zueinander führt, das i-te Symbol in der ersten Zeichenfolge (geordnet nach Index des ersten Auftretens) dem i-ten Symbol in der zweiten Zeichenfolge (wieder geordnet) zuordnen muss nach Index des ersten Auftretens). Dieses Prinzip kann verwendet werden, um eine Permutation zu erstellen, sie auf die erste Zeichenfolge anzuwenden und dann auf Gleichheit mit der zweiten Zeichenfolge zu überprüfen - wenn sie gleich sind, sind sie äquivalent, andernfalls nicht.

Hier ist eine mögliche Implementierung:

%Vor%

Wie Sie bereits gesagt haben, wird unter Äquivalenzbedingungen auf Gleichheit der Zeichenketten geachtet, aber es ist die halbe Miete. Wenn Sie eine kanonische Form für mathematische Ausdrücke hätten, könnten Sie diesen Ansatz für zwei Ausdrücke in kanonischer Form verwenden. Vielleicht könnte einer von Sympys Simplify das Richtige tun.

    
Amos Joshua 28.05.2011, 10:28
quelle
3

Statt über alle möglichen Permutationen zu iterieren, nehme man an, dass eine existiert und versuche, sie zu konstruieren. Ich glaube, dass das Scheitern des Algorithmus impliziert, dass die Permutation inexistent ist.

Hier ist der Grundriss der auf die obigen Ausdrücke angewandten Idee:

lassen:

%Vor%

Wir suchen nach einer Permutation der Menge (A, C), die die Ausdrücke identisch machen würde. Rabelabel A und C wie X1 und X2 in der Reihenfolge ihres ersten Auftretens in str2, also:

%Vor%

weil C vor A in str2 erscheint. Als nächstes erstellen Sie das Array Y so, dass y [i] das i-te Symbol A oder C in der Reihenfolge des ersten Auftretens in str1 ist. Also:

%Vor%

Weil A vor C in str1 erscheint.

Konstruieren Sie nun str3 aus str2, indem Sie A und C durch X1 und X2 ersetzen:

%Vor%

Und dann beginne mit der Substitution von Xi für Y [i]. Zuerst wird X1 zu Y [1] = A:

%Vor%

Vergleichen Sie in diesem Stadium str3_1 und str1 mit dem ersten Auftreten eines der Xi's, in diesem Fall X2, weil diese beiden Strings gleich sind:

%Vor%

Sie haben eine Chance, die Permutation zu konstruieren. Wenn sie ungleich wären, hätten Sie bewiesen, dass es keine geeignete Permutation gibt (weil jede Permutation mindestens diese Substitution hätte vornehmen müssen) und könnten Ungleichheit herleiten. Aber sie sind gleich, also fahren Sie mit dem nächsten Schritt fort und ersetzen X2 durch Y [2] = C:

%Vor%

Und das ist gleich str1, also haben Sie Ihre Permutation (A- & gt; C, C- & gt; A) und haben die Äquivalenz der Ausdrücke gezeigt.

Dies ist nur eine Demonstration des Algorithmus für einen bestimmten Fall, aber er sollte verallgemeinern. Nicht sicher, was die niedrigste Reihenfolge, die Sie es bekommen konnten, ist, aber es sollte schneller sein als die n! Generieren aller Permutationen auf n Variablen.

Wenn ich die Bedeutung der Einheiten richtig verstehe, begrenzen sie, welche Variablen für welche anderen durch die Permutationen getauscht werden können. Also kann A in den obigen Ausdrücken durch C ersetzt werden, weil beide "m" -Einheiten haben, aber nicht mit B, das "s" -Einheiten hat. Sie können das folgendermaßen umgehen:

Konstruiere die Ausdrücke str1_m und str2_m aus str1 und str2, indem alle Symbole entfernt werden, die keine m Einheiten haben, und führe dann den obigen Algorithmus für str1_m und str2_m aus. Wenn die Konstruktion fehlschlägt, gibt es keine Permutation. Wenn die Konstruktion erfolgreich ist, behalte diese Permutation bei (nenne sie die m-Permutation) und konstruiere str1_s und str2_s aus str1 und str2, indem du alle Symbole entfernst, die keine s-Einheiten haben, dann führe den Algorithmus erneut für str1_s und str2_s aus. Wenn die Konstruktion fehlschlägt, sind sie nicht gleichwertig. Wenn es gelingt, wird die endgültige Permutation eine Kombination der m-Permutation und der s-Permutation sein (obwohl Sie wahrscheinlich nicht einmal es konstruieren müssen, Sie interessieren sich nur, dass es existiert).

    
Amos Joshua 27.05.2011 22:18
quelle
2

Wenn Sie eine Zeichenfolge an SymPys Funktion sympify() übergeben, werden automatisch die Symbole für Sie erstellt (Sie müssen sie nicht alle definieren).

%Vor%     
asmeurer 07.06.2011 04:24
quelle
1

Ich habe es einmal gemacht, in einem Simulator von Mathematics estudies .. Nun, in meinem Fall wusste ich, welche Variablen verwendet wurden.

Also habe ich das Ergebnis getestet und Werte in die Variablen eingefügt.

%Vor%

Und so lösen wir:

%Vor%

Wenn s1! = s2, wurde bewiesen, dass es keine Äquivalenz

gibt

Mit dieser Methode ist unmöglich sagen, dass zwei Ausdrücke äquivalent sind, Aber Sie können sagen, dass beides nicht äquivalent ist.

%Vor%

Nun .. ich hoffe, dass dir das weiterhilft.

    
JonatasTeixeira 27.05.2011 17:31
quelle
0

Dies ist, wie alle anderen bisherigen Antworten, keine robuste Lösung für das Problem, sondern enthält mehr hilfreiche Informationen für unseren zukünftigen akribischen Freund, um es zu lösen.

Ich gebe ein schwieriges Beispiel mit Eulers Formel Ссылка

Ich bin mir sicher, dass alle anderen Overflow-Antworten in meinem Beispiel nicht gelingen.

Ich zeige, dass auch alle Vorschläge auf der Webseite von sympy an meinem Beispiel scheitern. ( Ссылка )

%Vor%

MEHR NOTIZEN:

Ich vermute, dass dies ein schwieriges Problem ist, das generisch und robust zu lösen ist. Um die mathematische Äquivalenz richtig zu prüfen, müssen Sie nicht nur die Permutationen der Reihenfolge ausprobieren, sondern Sie müssen auch eine Bibliothek von mathematischen äquivalenten Transformationen haben und all diese Permutationen ausprobieren.

Ich glaube jedoch, dass dies ein lösbares Problem sein könnte, denn Wolfram Alpha scheint einen "alternativen Ausdruck" -Abschnitt zu haben, der den Trick macht, alle Permutationen die meiste Zeit über beliebige Ausdrücke mit diesen Äquivalenzen zu liefern.

IN ZUSAMMENFASSUNG:

Ich schlage folgendes vor mit der Erwartung, dass es bricht:

%Vor%     
D Adams 23.10.2015 17:09
quelle