Vandermonde Determinante

25

Bei einem gegebenen Vektor von nWerten (x1,x2,x3,...,xn)zurückkehren , die Determinante der entsprechenden Vandermonde-Matrix .

Diese Determinante kann wie folgt geschrieben werden:

Formel

Einzelheiten

Ihr Programm / Ihre Funktion muss eine Liste von Gleitkommazahlen in einem beliebigen geeigneten Format akzeptieren, das eine variable Länge zulässt, und die angegebene Determinante ausgeben.

Sie können davon ausgehen, dass sowohl die Eingabe als auch die Ausgabe im Bereich der von Ihrer Sprache unterstützten Werte liegt. Wenn Ihre Sprache keine Gleitkommazahlen unterstützt, können Sie ganze Zahlen annehmen.

Einige Testfälle

Es ist zu beachten, dass die Determinante immer dann ist, wenn zwei gleiche Einträge 0vorhanden sind , da in der entsprechenden Vandermonde-Matrix zwei gleiche Zeilen vorhanden sind. Vielen Dank an @randomra für den Hinweis auf diesen fehlenden Testfall.

[1,2,2,3]            0 
[-13513]             1
[1,2]                1
[2,1]               -1
[1,2,3]              2
[3,2,1]             -2
[1,2,3,4]           12
[1,2,3,4,5]        288
[1,2,4]              6
[1,2,4,8]         1008
[1,2,4,8,16]  20321280
[0, .1, .2,...,1]   6.6586e-028
[1, .5, .25, .125]  0.00384521
[.25, .5, 1, 2, 4]  19.3798828
Fehler
quelle
Können wir annehmen, dass die Eingabe mindestens die Länge 2 hat?
PurkkaKoodari
@ Pietu1998 Nein, siehe den ersten Testfall.
Alex A.
3
Wichtiger Testfall:: [1,2,2,3] => 0Zwei gleiche Elemente im Array, um zu testen, ob der Code die Selbstdifferenz ( xi-xi) überprüft, indem er nur mit verglichen wird 0.
Randomra
@randomra Vielen Dank, ich habe völlig vergessen, eine davon aufzunehmen. Immer wenn zwei Einträge gleich sind, ist die Determinante 0, da es zwei Mal die gleiche Zeile gibt.
Fehler
1
@flawr Die erwartete Ausgabe ergab sich aus Ihren Angaben. Ich schlug den Testfall vor, damit Antworten, die nicht für die gleiche Anzahl vorbereitet wurden, ihre Fehler leichter finden können.
Randomra

Antworten:

9

Gelee, 6 Bytes

œc2IFP

œc2Ruft alle Kombinationen ab, ohne die Länge 2 zu ersetzen. IBerechnet die Differenzliste jedes dieser Paare und ergibt eine Liste wie [[1], [2], [3], ..., [1]]. Wir Flatten und nehmen das PProdukt.

Probieren Sie es hier aus!

Lynn
quelle
8

Ruby, 49 47 Bytes

->x{eval(x.combination(2).map{|a,b|b-a}*?*)||1}

Dies ist eine Lambda-Funktion, die ein eindimensionales Array mit einem reellen Wert akzeptiert und je nach Art der Eingabe einen Gleitkommawert oder eine Ganzzahl zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu f.call(input).

Wir erhalten alle Kombinationen der Größe 2 mit .combination(2)und erhalten die Unterschiede für jedes Paar mit .map {|a, b| b - a}. Wir verbinden das resultierende Array in eine Zeichenfolge getrennt durch *, dann evaldieses, das das Produkt zurück. Wenn die Eingabe die Länge 1 hat, ist dies nil, was in Ruby falsch ist, so dass wir ||1in dieser Situation gerade am Ende 1 zurückgeben können. Beachten Sie, dass dies immer noch funktioniert, wenn das Produkt 0 ist, da 0 in Ruby aus irgendeinem Grund wahr ist.

Überprüfen Sie alle Testfälle online

2 Bytes gespart dank Doorknob!

Alex A.
quelle
7

Mathematica, 30 Bytes

1##&@@(#2-#&@@@#~Subsets~{2})&

Dies ist eine anonyme Funktion.

Erweitert um Mathematica ist es äquivalent zu (1 ##1 & ) @@ Apply[#2 - #1 & , Subsets[#1, {2}], {1}] &. 1##&ist eine Entsprechung für Times(Dankesseite), die auf jedes einzelne Elementpaar aus der von generierten Eingabeliste angewendet wird Subsets[list, {2}]. Beachten Sie, dass Subsetsdie Eindeutigkeit von Elementen nicht überprüft wird.

Feersum
quelle
5

J, 13 Bytes

-/ .*@(^/i.)#

Dies ist eine monadische Funktion, die ein Array aufnimmt und eine Zahl zurückgibt. Benutze es so:

  f =: -/ .*@(^/i.)#
  f 1 2 4
6

Erläuterung

Ich konstruiere explizit die dem Eingabearray zugeordnete Vandermonde-Matrix und berechne dann ihre Determinante.

-/ .*@(^/i.)#   Denote input by y
            #   Length of y, say n
         i.     Range from 0 to n - 1
       ^/       Direct product of y with the above range using ^ (power)
                This gives the Vandermonde matrix
                 1 y0     y0^2     ... y0^(n-1)
                 1 y1     y1^2     ... y1^(n-1)
                   ...
                 1 y(n-1) y(n-1)^2 ... y(n-1)^(n-1)
-/ .*           Evaluate the determinant of this matrix
Zgarb
quelle
Ich dachte, Leerzeichen wären in J ...
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Die Determinante ist ein Sonderfall, der ein Trennzeichen erfordert, da .es sich auch um ein Modifikatorzeichen handelt. Gleiches für sich :.
Zgarb
Oh! Das ist cool.
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Eigentlich denke ich, dass genau das J uncool macht. J steht für Jot, dh einen Punkt oder einen kleinen Ring (APL's ), wie beim Jotting mit J ... Das unglaublich überladene .und :(was wiederum optisch dasselbe wie zwei gestapelte .s ist) macht J (für mich) schwer lesbar. Umso mehr, wenn Leerzeichen neben den Punkten die Bedeutung bestimmen! Js .müssen das am meisten überladene Symbol in der gesamten Computergeschichte sein: Ich zähle 53 verschiedene Bedeutungen von .und 43 (61, wenn Sie alle _9:bis zählen 9:) verschiedene Bedeutungen von :. Yukk. ;-)
Adám
@ Nᴮᶻ es kann hilfreich sein, an die zu denken. als sein eigenes Zeichen; daher könnte es ohne ein Leerzeichen mit einem anderen Operator verwechselt werden. Wenn J nicht für dich ist, ist das verständlich.
Conor O'Brien
4

MATL , 9

!G-qZRQpp

Probieren Sie es online!

Dadurch wird eine Matrix aller Unterschiede berechnet, und es wird nur der Teil unterhalb der Hauptdiagonale beibehalten, sodass die anderen Einträge 1das Produkt nicht beeinträchtigen. Die untere Dreiecksfunktion macht die unerwünschten Elemente 0nicht 1. Also subtrahieren wir 1, nehmen den unteren dreieckigen Teil und addieren 1zurück. Dann können wir das Produkt aus allen Einträgen entnehmen.

t     % take input. Transpose
G     % push input again
-     % subtract with broadccast: matrix of all pairwise differences
q     % subtract 1
ZR    % make zero all values on the diagonal and above
Q     % add 1
p     % product of all columns
p     % product of all those products
Luis Mendo
quelle
Es ist bedauerlich, aber es 2Xn!dpscheint nur mit einzelnen Werten zu funktionieren, wenn der Wert größer oder gleich 2 ist ... Ich hatte es selbst geschrieben und versucht, Jelly zu schlagen: P
FryAmTheEggman
@FryAmTheEggman Awww. Du hast recht. Danke für das Heads-up!
Luis Mendo
Ja, ich dachte, das wäre das Problem. Ich würde versuchen, so etwas wie einen Wrapper hinzuzufügen, wenn Sie Xneine Überprüfung durchführen müssen if size(arg) == [1,1] ...oder so. Ich bin zu faul, um durch die Quelle zu schauen, aber (hoffentlich) sollte es nicht so schwierig sein.
FryAmTheEggman
@FryAmTheEggman Tatsächlich bin ich mir nicht sicher, ob das das Problem ist (deshalb habe ich meinen Kommentar schnell bearbeitet). Wenn die erste Eingabe eine Zahl ist, sollte die zweite Eingabe 1oder sein, 0und es macht dann keinen Unterschied, ob die erste Eingabe als Array oder als Zahl interpretiert wird. Das eigentliche Problem ist, dass die zweite Eingabe die Array-Größe nicht überschreiten kann. Msgstr "Wie viele Möglichkeiten gibt es, 2 Elemente aus 1 Element auszuwählen?" In diesem Fall ist der Unterschied zwischen Array und Nummer von Bedeutung: Wenn die erste Eingabe eine Array-Rückgabe ist [](leeres Array), ist es eine Zahlenrückgabe 0. Ich denke, ich werde zurückkehren [], weil dann pdie andere Interpretation
erzwungen wird
@FryAmTheEggman Ich denke, ich werde die Funktion in zwei Versionen aufteilen. Danke noch einmal!
Luis Mendo
3

Pyth, 15 13 12 11 Bytes

*F+1-M.c_Q2
         Q    take input (in format [1,2,3,...])
        _     reverse the array: later we will be subtracting, and we want to
                subtract earlier elements from later elements
      .c  2   combinations of length 2: this gets the correct pairs
    -M        map a[0] - a[1] over each subarray
  +1          prepend a 1 to the array: this does not change the following
                result, but prevents an error on empty array
*F            fold over multiply (multiply all numbers in array)

Vielen Dank an @FryAmTheEggman und @ Pietu1998 für jeweils ein Byte!

Türknauf
quelle
1
* F auf einem leeren Array sollte wirklich 1. sein
Lirtosiast
3

Mathematica, 32 Bytes

Det@Table[#^j,{j,0,Length@#-1}]&

Ich war überrascht, dass ich kein eingebautes Gerät für Vandermonde gefunden habe. Wahrscheinlich, weil es so einfach ist, es selbst zu machen.

Dieser konstruiert explizit die Transponierung einer VM und nimmt ihre Determinante (die natürlich mit der des Originals identisch ist). Diese Methode erwies sich als erheblich kürzer als die Verwendung einer mir bekannten Formel.

Hypotenuser
quelle
3

Haskell, 34 Bytes

f(h:t)=f t*product[x-h|x<-t]
f _=1

Eine rekursive Lösung. Wenn ein neues Element hvorangestellt wird, wird der Ausdruck x-hfür jedes Element xder Liste mit dem Produkt von multipliziert . Danke an Zgarb für 1 Byte.

xnor
quelle
2

Matlab, 26 Bytes

(nicht konkurrierend)

Einfache Verwendung von Builtins. Beachten Sie, dass Matlab's (noch einmal) vanderVandermonde-Matrizen erstellt, wobei jedoch die Reihenfolge der Zeilen vertauscht wird.

@(v)det(fliplr(vander(v)))
Fehler
quelle
2
Warum nicht konkurrieren?
Alex A.
3
Da ich derjenige bin, der diese Herausforderung gemeistert hat, wollte ich dies nur zur Verfügung stellen, damit die Leute ihre eigenen Beispiele ausprobieren können.
Fehler
Ist nicht Det (gespiegelte Zeilen) = (-1) ^ n Det (Original)?
Hypotenuser
Ich bin nicht ganz sicher, wie die Determinante wechselt, wenn Sie zwei Spalten oder Zeilen wechseln.
Fehler
@hYPotenuser - Ersetze n durch n + 1. Alles, was Sie tun, ist das Multiplizieren mit einer Matrix P, die aus Nullen besteht, mit Ausnahme der Diagonale, die von links unten nach rechts oben verläuft (Sie möchten also det (P * vander (v)) = det (P) det (vander (v ))). Wenn Sie die erste Spalte oder etwas anderes erweitern, sehen Sie det (P) = (-1) ^ (n + 1).
Batman
2

Rust, 86 Bytes

|a:Vec<f32>|(0..a.len()).flat_map(|x|(x+1..a.len()).map(move|y|y-x)).fold(1,|a,b|a*b);

Rust, wortreich wie immer ...

Die Erklärung wird später kommen (es ist jedoch ziemlich einfach).

Türknauf
quelle
2

Perl, 38 41 Bytes

Fügen Sie +1 für -p

Geben Sie die Zahlen in einer Zeile auf STDIN ein. Also zB laufen als

perl -p vandermonde.pl <<< "1 2 4 8"

Benutze einen bösen Regex, um die doppelte Schleife zu erhalten:

vandermonde.pl:

$n=1;/(^| ).* (??{$n*=$'-$&;A})/;*_=n
Tonne Hospel
quelle
2

JavaScript (ES6), 61 Byte

a=>a.reduce((p,x,i)=>a.slice(0,i).reduce((p,y)=>p*(x-y),p),1)

Ich habe versucht, ein Array zu verstehen (Firefox 30-57) und es war 5 Bytes länger:

a=>[for(i of a.keys(p=1))for(j of Array(i).keys())p*=a[i]-a[j]]&&p

Die langweilige verschachtelte Schleife ist jedoch wahrscheinlich kürzer.

Neil
quelle
1

Haskell, 53 Bytes

 f x=product[x!!j-x!!i|j<-[1..length x-1],i<-[0..j-1]]

Anwendungsbeispiel: f [1,2,4,8,16]-> 20321280.

Gehen Sie die Indizes jund iin einer verschachtelten Schleife durch und erstellen Sie eine Liste der Unterschiede der Elemente an Position jund i. Machen Sie das Produkt aus allen Elementen in der Liste.

Andere Varianten, die sich als etwas länger herausstellten:

f x=product[last l-i|l<-scanl1(++)$pure<$>x,i<-init l]54 Bytes

import Data.List;f i=product[y-x|[x,y]<-subsequences i]55 Bytes

nimi
quelle
1

CJam, 16 Bytes

1l~{)1$f-@+:*\}h

Als Antwort auf den Beitrag von A Simmons , obwohl CJam keinen Kombinationsoperator hat, ist es möglich, es besser zu machen :)

-1 Byte Danke an @ MartinBüttner.

Versuchen Sie es online | Testsuite

1                   Push 1 to kick off product
 l~                 Read and evaluate input V
   {          }h    Do-while loop until V is empty
    )                 Pop last element of V
     1$               Copy the prefix
       f-             Element-wise subtract each from the popped element
         @+           Add the current product to the resulting array
           :*         Take product to produce new product
             \        Swap, putting V back on top
Sp3000
quelle
0

CJam, 32 Bytes

1q~La\{1$f++}/{,2=},{~-}%~]La-:*

Ich bin sicher, dass jemand in CJam besser Golf spielen kann ... Das Hauptproblem ist, dass ich keinen guten Weg sehe, um die Teilmengen zu erhalten, die den größten Teil meiner Bytes verbrauchen. Dies erzeugt den Kraftsatz (nach einer Idee von Martin Büttner) und wählt dann die Elemente der Länge 2 aus.

Ein Simmons
quelle
0

R , 41 Bytes

function(v)det(outer(v,1:sum(v|1)-1,"^"))

Probieren Sie es online!

Ich war überrascht, hier keine Antwort von R zu sehen!

Giuseppe
quelle