Vereinfachen und partielle Ableitung einer Polynomzeichenfolge

8

Einführung

Schreiben Sie ein Programm, um die partielle Ableitung eines Polynoms (möglicherweise multivariat) in Bezug auf eine Variable zu berechnen.

Herausforderung

Derivate sind sehr wichtige mathematische Werkzeuge, die in der Physik, Chemie, Biologie, Wirtschaft, Psychologie und anderen Bereichen weit verbreitet sind, um alle Arten von Problemen zu lösen. Ausdrücke mit mehreren Variablen sind ebenfalls sehr häufig.

Im Rahmen dieser Herausforderung wird eine Polynomzeichenfolge ("polystr") durch die folgende BNF (Backus-Naur-Form) definiert:

<polystr> ::= <term> | <term><plusminus><polystr>

<plusminus> ::= "+" | "-"

<term> ::= <coeff> | <coeff><baseterm> | <baseterm>

<baseterm> ::= <variable> | <variable><exponent> | <baseterm><baseterm>

<coeff> ::= positive_integer

<exponent> ::= positive_integer

<variable> ::= lowercase_ASCII_letters

Wo positive_integerund lowercase_ASCII_letterssind ganz selbsterklärend.

Zum Beispiel 3x2y-x3y-x2y+5bedeutet die Zeichenfolge 3*(x^2)*y-(x^3)*y-(x^2)*y+5. Die in der Eingabe angegebenen Begriffe können in beliebiger Reihenfolge angezeigt werden, und die Variablen in jedem Begriff können auch in beliebiger Reihenfolge angezeigt werden. So ist zum Beispiel 5-yx2-x3y+y3x2auch eine gültige Eingabe und ist in der Tat die gleiche wie im vorherigen Beispiel.

Die Regel für die partielle Ableitung lautet, dies nur Begriff für Begriff zu tun. Wenn die Variable nicht im Term erscheint, ist die Ableitung Null. Andernfalls wird der Koeffizient des Terms mit dem Exponenten dieser Variablen multipliziert, und dann wird der Exponent der Variablen um eins verringert. Die Exponenten für andere Variablen ändern sich nicht. Dies folgt nur der Definition in der Mathematik. Wenn der resultierende Exponent Null ist, entfernen Sie außerdem die Variable aus dem Term.

Zum Beispiel, um die partielle Ableitung von 5z-z2y2-5w3yin Bezug auf zu nehmen y. Der folgende Vorgang wird durchgeführt (gemäß dem oben definierten BNF werden die "Koeffizienten" alle als positive Zahlen angenommen, dh die Vorzeichen werden separat betrachtet)

          5z          -   z2y2        - 5w3y

Coeff                 1->1*2=2      5->5*1=5
Expon                 2->2-1=1      1->1-1=0
Term                  -   2yz2         - 5w3 
      (y is not here            (expon 0->y removed)
     so the term is 0)

Das Ergebnis ist -2yz2-5w3y.

Wenn andererseits der obige Ausdruck in Bezug auf teilweise abgeleitet wird a, ist das Ergebnis, 0weil er ain keinem der Begriffe enthalten ist.

Ihre Aufgabe ist es, eine Funktion oder ein vollständiges Programm zu schreiben, um diese Ableitung zu berechnen. Es sollte eine Polynomzeichenfolge und ein einzelnes Zeichen (die Variable, für die eine Ableitung vorgenommen werden soll) annehmen und die Ableitung in der einfachsten Form zurückgeben.

"Einfachste Form" bedeutet drei Dinge.

  1. Die Zahl 0(nicht die Ziffer) sollte nicht in der Ausgabe erscheinen, es sei denn, die Ausgabe selbst ist gerecht 0. Also weder 0+10ynoch 3-y0zgültig ausgegeben werden und sollte umgewandelt werden 10yund 3-zsind.

  2. Die Zahl 1sollte nicht als Exponent oder Koeffizient erscheinen, sondern kann selbst als eigenständiger Begriff erscheinen.

  3. Die Begriffe mit genau demselben Satz von Variablen und Exponenten sollten zusammengeführt werden, was bedeutet, dass dies 3a2b5-4b5a2keine gültige Ausgabe ist und -a2b5stattdessen erfolgen sollte. Weitere Informationen zur Ein- und Ausgabe finden Sie im Abschnitt "Technische Daten".

Testfälle

Input
Output

2xy+4ax-5+7mx4-4-7x4m, x
2y+4a

4upv+5u2v3w4-4w4u2v3+qr-v,v
4up+3u2v2w4-1

12ux-7x2m3+ab5,q
0

-a+10ca11y-1nv3rt3d-poly, a
-1+110ca10y

1y+1x3y, y
1+x3

Technische Daten

  • Die Eingabe kann über Standardformulare erfolgen . Mit anderen Worten, Sie können Eingaben als Zeichenfolge, als Liste von Zeichen, als verschachteltes Array von Koeffizienten, Variablen (möglicherweise gekennzeichnet durch ihren ASCII-Wert minus 'a' oder ähnliches) und Exponenten usw. verwenden. Sie können auch Änderungen vornehmen die Saite zu 2*x^3y^2oder gleich statt 2x3y2.

Verwenden Sie jedoch nicht die Eingabe [2,0,0,0,1,0,0,3,0,0,...0](ein Array mit 27 Elementen) für den Begriff 2dgoder ein anderes ausführliches Format, das die 26 Buchstaben wie folgt auflistet. Ihr Eingabeformat sollte auch in der Lage sein , zu behandeln , abund baals verschiedene Eingänge (so dass das 27-Element - Array - Format aufgrund dieser Beschränkung ungültig ist als auch).

  • Jede Variable (Buchstabe) wird in jedem Term der Eingabe nur einmal angezeigt. Das bedeutet, dass xxsie nicht angezeigt wird und immer als dargestellt wird, und dass auch nichts x2Ähnliches a3b4a2angezeigt wird.

  • Zur Wiederholung können die Begriffe in der Eingabe in beliebiger Reihenfolge angezeigt werden.

  • Sie können auch das Ausgabeformat frei wählen, sofern das oben erwähnte ausführliche Format vermieden wird. Die Ausgabe sollte jedoch immer in der einfachsten Form wie oben definiert sein. Genau wie bei der Eingabe können die Begriffe in der Ausgabe in beliebiger Reihenfolge angezeigt werden, und die Variablen in jedem Begriff können auch in beliebiger Reihenfolge angezeigt werden und müssen nicht zwischen den Begriffen konsistent sein. Das heißt, es pu+2up2ist eine gültige Ausgabe. Das Vorzeichen für den führenden Begriff kann entweder positiv oder negativ sein -y+3xund 3x-yist beide gültig +3x-y.

  • Die Eingabe wird immer so angegeben, dass alle Koeffizienten und Exponenten in der Ausgabe kleiner als 2 32 -1 sind oder die größte Ganzzahl, die Ihre Sprache verarbeiten kann, je nachdem, welcher Wert kleiner ist. Die Behauptung, dass die größte Ganzzahl, die Ihre Sprache verarbeiten kann, unangemessen klein ist und die Trivialisierung der Herausforderung in die Kategorie der Standardschlupflöcher fällt.

  • Dies ist , die niedrigste Anzahl von Bytes gewinnt.

  • Wie üblich gelten hier Standardlücken .

Bearbeiten: Da sich die meisten Antworten bisher als Interna herausstellen, die die ganze Herausforderung bewältigen, und obwohl ich weiß, dass es eingebaute Funktionen gibt, habe ich nicht die Absicht, solche Interna von Anfang an zu verbieten, und ich habe es jetzt auch nicht getan. Ich werde die Gewinnkriterien zu einem Kriterium machen, das auf einer sprachbasierten Basis basiert, dh die Einreichung mit den geringsten Bytes in jeder Sprache gewinnt in dieser Sprache. Ich werde ein Standard-Snippet für einen Katalog hinzufügen, wenn genügend Einreichungen vorhanden sind. Sie können weiterhin eingebaute Antworten einreichen, um die Leistungsfähigkeit Ihrer Sprache zu demonstrieren. Zögern Sie jedoch nicht, Ihre nicht eingebauten Antworten einzureichen, auch wenn diese viel länger sind und Ihre Sprache keine eingebauten Antworten enthält. Viel Spaß beim Code-Golfen in Ihrer Lieblingssprache!

Weijun Zhou
quelle
@JonathanFrech Der zweite und der dritte Term in der Eingabe können zusammengeführt werden. Zusammen geben sie den zweiten Term in der Ausgabe.
Weijun Zhou
Ah, okay. Warum wird -9in Ihrem ersten Beispiel in der Ausgabe angezeigt?
Jonathan Frech
1
Der einzige Grund, warum Sie in der Ausgabe zusammenführen können, ist, dass die Eingabe bereits zusammengeführt werden konnte. Das macht dies wirklich zu einer Kombination aus 2 unabhängigen Problemen take derivativeundmerge
Ton Hospel
Ich nehme an, die einfachste Form impliziert auch no exponent 1, obwohl Sie dies nicht zu sagen scheinen
Ton Hospel
@ JonathanFrech Das ist ein Tippfehler. Fest.
Weijun Zhou

Antworten:

2

Python 2 , 252 245 Bytes

o,d=input()
D={};s=''
for c,t in o:T=`sorted(t)`;D[T]=D.get(T,0)+c
for t in D:
 c,t=D[t],dict(eval(t))
 if(d in t)*c:e=t[d];c*=e;t[d]=e-1;s+=('%+d '%c)[:~((-2<c<2)*sum(t.values())>0)]+''.join((v+`t[v]`*(t[v]>1))*(t[v]>0)for v in t)
print s or'0'

Probieren Sie es online aus!

Nimmt die Eingabe als verschachtelte Liste von Koeffizienten und Begriffen auf:

[
 [coeff1, [[var1_1,exp1_1],
           [var1_2,exp1_2],
           ... ]
 ],
 [coeff2, [[var2_1,exp2_1], ...]],
 ...
]

Zum Beispiel wird das erste Beispiel ( 5z-z2y2-5w3y) wie folgt angegeben:

[
 [ 5, [['z', 1]          ] ], 
 [-1, [['z', 2], ['y', 2]] ],
 [-5, [['w', 3], ['y', 1]] ]
]

Die Fußzeile enthält eine Funktion, die eine Zeichenfolgeneingabe im gewünschten Eingabeformat analysiert : parse(s).


Bearbeiten:

  • Nimmt Eingabe statt Funktion
TFeld
quelle
2

Retina , 249 233 Bytes

(.)(?=.*¶\1$)
$&_
L`.\w*
G`_
^\b
+
%O`._?\d*
_\d+
*
\b[a-z]
1$&
\b(\d+)(?=.*?(_+))
$1*$2
O$`(.)_+(.+)
$2$1
+`((\+|-)_+)(.*)¶\2(_+\3)\b
$1$4
+`\+_(_*(.*)¶-)_(_*\2\b)
+$1$3
G`\b_
\b_+
$.&
_(__+)
$.1
^\+|¶|(.)__|._
$1
\b1([a-z])
$1
^$
0

Probieren Sie es online aus! Link enthält Testfälle. Erläuterung:

(.)(?=.*¶\1$)
$&_

Fügen Sie _nach jedem Auftreten der angegebenen Variablen ein hinzu.

L`.\w*

Teilen Sie die Eingabe in Begriffe auf.

G`_

Behalten Sie nur die Begriffe bei, die auf die Variable verwiesen haben.

^\b
+

Präfix a, +wenn der erste Begriff kein Vorzeichen hat.

%O`._?\d*

Sortieren Sie jeden Begriff alphabetisch. (Das Schild stimmt überein, aber das ist kein Problem; es sortiert sowieso am Anfang.)

_\d+
*

Konvertieren Sie alle Exponenten der Variablen in unär.

\b[a-z]
1$&

Stellen Sie diesen Begriffen vorübergehend 1 ohne Multiplikator voran.

\b(\d+)(?=.*?(_+))
$1*$2

Multiplizieren Sie den Multiplikator mit dem Exponenten der Variablen und lassen Sie das Ergebnis unär.

O$`(.)_+(.+)
$2$1

Sortieren Sie alle Begriffe.

+`((\+|-)_+)(.*)¶\2(_+\3)\b
$1$4

Fügen Sie Begriffe mit demselben Zeichen hinzu.

+`\+_(_*(.*)¶-)_(_*\2\b)
+$1$3

Subtrahieren Sie Begriffe mit unterschiedlichen Vorzeichen.

G`\b_

Entfernen Sie Begriffe, die durch einen Begriff mit einem anderen Zeichen storniert wurden.

\b_+
$.&

Konvertieren Sie den Multiplikator zurück in eine Dezimalzahl.

_(__+)
$.1

Dekrementieren Sie Exponenten größer als drei und konvertieren Sie sie zurück in Dezimalzahlen.

^\+|¶|(.)__|._
$1

a) Entfernen Sie ein führendes +Vorzeichen. b) Verbinden Sie alle Begriffe wieder miteinander. c) Konvertieren Sie die Quadrate der Variablen in die einfache Variable. d) Entfernen Sie die Variable, wenn sie keinen Exponenten hat.

\b1([a-z])
$1

Entfernen Sie die temporäre 1, es sei denn, sie muss nicht mehr multipliziert werden.

^$
0

Wenn keine Begriffe mehr vorhanden sind, ist das Ergebnis Null.

Die Unterstützung doppelter Begriffe kostet fast die Hälfte meiner Byteanzahl. Vorherige 123-Byte-Lösung, bei der Begriffe nicht dedupliziert wurden:

(.)(?=.*¶\1$)
$&_
L`.\w*
G`_
_\d+
*
\b[a-z]
1$&
\b(\d+)(?=.*?(_+))
$.($1*$2
_(__+)
$.1
^\+|¶|(.)__|._
$1
\b1([a-z])
$1
^$
0

Probieren Sie es online aus! Erläuterung:

(.)(?=.*¶\1$)
$&_

Fügen Sie _nach jedem Auftreten der angegebenen Variablen ein hinzu.

L`.\w*

Teilen Sie die Eingabe in Begriffe auf.

G`_

Behalten Sie nur die Begriffe bei, die auf die Variable verwiesen haben.

_\d+
*

Konvertieren Sie alle Exponenten der Variablen in unär.

\b[a-z]
1$&

Stellen Sie diesen Begriffen vorübergehend 1 ohne Multiplikator voran.

\b(\d+)(?=.*?(_+))
$.($1*$2

Multiplizieren Sie den Multiplikator mit dem Exponenten der Variablen.

_(__+)
$.1

Dekrementieren Sie Exponenten größer als drei und konvertieren Sie sie zurück in Dezimalzahlen.

^\+|¶|(.)__|._
$1

a) Entfernen Sie ein führendes +Vorzeichen. b) Verbinden Sie alle Begriffe wieder miteinander. c) Konvertieren Sie die Quadrate der Variablen in die einfache Variable. d) Entfernen Sie die Variable, wenn sie keinen Exponenten hat.

\b1([a-z])
$1

Entfernen Sie die temporäre 1, es sei denn, sie muss nicht mehr multipliziert werden.

^$
0

Wenn keine Begriffe mehr vorhanden sind, ist das Ergebnis Null.

Neil
quelle
Beeindruckend, aber Sie müssen diese beiden Begriffe in Ihrem TIO-Beispiel zusammenführen.
Weijun Zhou
1
@WeijunZhou Entschuldigung, ich hatte diesen Teil der Spezifikation übersehen. Lassen Sie mich darüber nachdenken ...
Neil
@WeijunZhou Ugh, es hat mich viel zu viele Bytes gekostet, aber ich denke, ich habe es zum Laufen gebracht.
Neil
Vielen Dank für Ihre beeindruckende harte Arbeit. Ich denke, dies ist ein guter Punkt für mich, um Retina zu lernen.
Weijun Zhou
0

Physica , 3 Bytes

Dies verwendet keine neue Funktion. und seine reine ASCII-Alternative Differentiatewurden vor mehr als 10 Tagen eingeführt .

Demo

Angenommen, sowohl der Ausdruck als auch die Variable werden als Zeichenfolge übergeben. Testcode:

f = ∂

Print[f['2*x*y+4*a*x-5+7*m*x^4-4-7*x^4*m'; 'x']]
Print[f['4*u*p*v+5*u^2*v^3*w^4-4*w^4*u^2*v^3+q*r-v'; 'v']]
Print[f['-a+10*c*a^11*y-1*n*v^3*r*t^3*d-p*o*l*y'; 'a']]

Genaue Ausgabe:

4*a + 2*y
4*p*u + 3*u**2*v**2*w**4 - 1
110*a**10*c*y - 1

Ausdrucksformat: *zur Multiplikation, **zur Exponentiation +und -zur entsprechenden Addition und Subtraktion.

Physica - Visuelle Demo

Mr. Xcoder
quelle