Bei zwei nicht leeren Listen mit ganzen Zahlen sollte Ihre Übermittlung die diskrete Faltung der beiden berechnen und zurückgeben . Wenn Sie Listenelemente als Koeffizienten von Polynomen betrachten, repräsentiert die Faltung der beiden Listen interessanterweise die Koeffizienten des Produkts der beiden Polynome.
Definition
In Anbetracht der Listen A=[a(0),a(1),a(2),...,a(n)]
und B=[b(0),b(1),b(2),...,b(m)]
(Setzen a(k)=0 for k<0 and k>n
und b(k)=0 for k<0 and k>m
) ist die Faltung der beiden als A*B=[c(0),c(1),...,c(m+n)]
wo definiertc(k) = sum [ a(x)*b(y) for all integers x y such that x+y=k]
Regeln
- Beliebige bequeme Eingabe- und Ausgabeformate für Ihre Sprache sind zulässig.
- Integrierte Funktionen für Faltung, Erstellung von Faltungsmatrizen, Korrelation und Polynommultiplikation sind nicht zulässig.
Beispiele
[1,1]*[1] = [1,1]
[1,1]*[1,1] = [1,2,1]
[1,1]*[1,2,1] = [1,3,3,1]
[1,1]*[1,3,3,1] = [1,4,6,4,1]
[1,1]*[1,4,6,4,1] = [1,5,10,10,5,1]
[1,-1]*[1,1,1,1,1] = [1,0,0,0,0,-1]
[80085,1337]*[-24319,406] = [-1947587115,7,542822]
code-golf
math
array-manipulation
number-theory
polynomials
fehlerhaft
quelle
quelle
[1,1]*[] = []
und kann möglicherweise nicht für gelten[]*[] = ?
. Faltung ist in leeren Listen nicht genau definiert. Ich denke, Sie sollten garantieren, dass die Eingabelisten nicht leer sind.Antworten:
J
108 BytesVerwendung:
Beschreibung: Das Programm nimmt zwei Listen auf, erstellt eine Multiplikationstabelle und addiert die Zahlen zu den positiven Diagonalen.
quelle
MATL , 19 Bytes
Probieren Sie es online!
Erläuterung
Dadurch wird eine Blockdiagonalmatrix mit den beiden Eingängen erstellt, wobei der erste umgekehrt wird. Bei Eingaben
[1 4 3 5]
ist[1 3 2]
die Matrix beispielsweiseJeder Eintrag der Faltung wird erhalten, indem die erste Reihe um eine Position nach rechts verschoben, das Produkt jeder Spalte berechnet und alle Ergebnisse summiert werden.
Grundsätzlich sollte die Verschiebung mit Nullen von links aufgefüllt werden. Entsprechend kann die Umlaufverschiebung verwendet werden, da die Matrix an den entsprechenden Einträgen Nullen enthält.
Zum Beispiel wird das erste Ergebnis aus der verschobenen Matrix erhalten
und ist so
1*1 == 1
. Die Sekunde wird von erhaltenund ist damit
4*1+1*3 == 7
usw. Dies mussm+n-1
mal gemacht werden, wom
undn
sind die Eingangslängen. Der Code verwendet eine Schleife mitm+n
Iterationen (die einige Bytes einsparen) und verwirft das letzte Ergebnis.quelle
Haskell,
5549 BytesDefiniert einen Operator
#
.quelle
[0,0..]
kann sein(0<$b)
, um genau die benötigte Länge zu geben, die das leere Basisgehäuse zulässt_#b=0<$b
.Matlab / Octave, 41 Bytes
Dies definiert eine anonyme Funktion. Um es aufzurufen, weisen Sie es einer Variablen zu oder verwenden Sie
ans
.Probieren Sie es hier aus .
Erläuterung
Dies nutzt die Fakten, die
Der Code berechnet die Wurzeln der beiden Polynome (Funktion
roots
) und verknüpft sie zu einem Spaltenarray. Daraus erhält er die Koeffizienten des Produktpolynoms mit einer führenden1
(Funktionpoly
). Schließlich wird das Ergebnis mit den führenden Koeffizienten der beiden Polynome multipliziert.quelle
Oktave , 48 Bytes
Probieren Sie es hier aus .
Erläuterung
Die diskrete Faltung entspricht der Multiplikation der (zeitdiskreten) Fouriertransformationen. Eine Möglichkeit, die Polynome zu multiplizieren, besteht darin, sie zu transformieren, die transformierten Sequenzen zu multiplizieren und zurück zu transformieren.
Wenn die diskrete Fouriertransformation (DFT) anstelle der Fouriertransformation verwendet wird, ist das Ergebnis die zirkuläre Faltung der ursprünglichen Folgen von Polynomkoeffizienten. Der Code folgt dieser Route. Damit die Kreisfaltung der Standardfaltung entspricht, werden die Sequenzen mit Nullen aufgefüllt und das Ergebnis wird getrimmt.
quelle
05AB1E ,
1817 BytesCode
Erläuterung
Die Theorie dahinter:
Um die Faltung zu finden, lassen Sie uns das Beispiel nehmen
[1, 2, 3]
,[3, 4, 5]
. Wir positionieren die Werte des ersten Arrays verkehrt herum und vertikal wie folgt:Jetzt platzieren wir das zweite Array wie eine Leiter und multiplizieren es mit:
Resultierend in:
Dann addieren wir sie zu:
Die Faltung ist also
[3, 10, 22, 22, 15]
.Der Code selbst:
Wir werden dies Schritt für Schritt mit dem
[1, 2, 3]
,[3, 4, 5]
als Testfall durchführen.Wir drücken zuerst
0
undE
bewerten dann das erste Eingabearray. Wir bilden jedes Element mit abv
.Also drücken wir für jedes Element das zweite Array mit
²
und dann die Länge des ersten Arrays mit¹g
und verringern diese um 1 (mit<
). Wir wandeln dies in eine Liste von Nullen mit (Länge 1. Array - 1) Nullen umÅ0
und fügen dies unserer Liste hinzu. Unser Stack sieht jetzt für das erste Element in der Eingabeliste so aus:Wir multiplizieren dieses Array mit dem aktuellen Element
y*
. Danach drücken wirN
, was den Index des aktuellen Elements angibt (null-indiziert) und drehen das Array mit um ein Vielfaches nach rechtsFÁ}
. Schließlich addieren wir dies zu unserem Anfangswert (0
). Im Grunde wird also Folgendes getan:Welches wird dann implizit gedruckt. Verwendet die CP-1252- Codierung. Probieren Sie es online! .
quelle
Gelee , 9 Bytes
Probieren Sie es online! oder überprüfen Sie alle Testfälle .
Wie es funktioniert
quelle
Schale , 5 Bytes
Probieren Sie es online!
Hinweis: Wenn Sie die Nullpolynom- / Leerliste bereitstellen, müssen Sie deren Typ angeben (z. B.
[]:LN
)!Erläuterung
quelle
Matlab, 33 Bytes
Probieren Sie es online!
Erstellt eine Matrix aller elementweisen Produkte der Eingaben und summiert dann entlang der Diagonalen. Am
,1
Ende wird matlab gezwungen, in der richtigen Richtung zu summieren, wenn einer der Eingabevektoren die Länge 1 hat.In Octave
spdiags
funktioniert dies nicht für Vektoren, was zu einem Fehler führt, wenn einer der Eingänge die Länge 1 hat. Matlab 2016b oder neuer wird für die explizite Erweiterung des elementweisen Produkts benötigt.quelle
Ruby, 83 Bytes
Fast direkt aus einer Antwort herausgezogen, die ich zuvor in Bezug auf das Erweitern von Wurzeln in ein Polynom gemacht habe .
quelle
Python, 90 Bytes
quelle
JavaScript (ES6), 64 Byte
Gibt das leere Array zurück, wenn eine der Eingaben leer ist. Basierend auf meiner Antwort auf Polynomialception .
quelle
Julia,
62-55BytesProbieren Sie es online!
quelle
Clojure, 104 Bytes
Das Zusammenführen zu
sorted-map
garantiert, dass die Werte in der richtigen Reihenfolge zurückgegeben werden. Ich wünschte, es gäbe noch ein paar Testfälle.quelle