Determinant Vandermonde

25

Podany wektor nwartości (x1,x2,x3,...,xn)zwraca wyznacznik odpowiedniej macierzy Vandermonde .

Tę determinantę można zapisać jako:

formuła

Detale

Twój program / funkcja musi zaakceptować listę liczb zmiennoprzecinkowych w dowolnym dogodnym formacie, który pozwala na zmienną długość, i wyprowadzić określoną determinantę.

Możesz założyć, że dane wejściowe i wyjściowe mieszczą się w zakresie wartości obsługiwanych przez Twój język. Jeśli Twój język nie obsługuje liczb zmiennoprzecinkowych, możesz założyć liczby całkowite.

Niektóre przypadki testowe

Zauważ, że ilekroć są dwa równe wpisy, wyznacznikiem będzie, 0ponieważ w odpowiedniej macierzy Vandermonde znajdują się dwa równe rzędy. Dzięki @randomra za wskazanie tej brakującej skrzynki testowej.

[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
wada
źródło
Czy możemy założyć, że dane wejściowe mają co najmniej długość 2?
PurkkaKoodari
@ Pietu1998 Nie, zobacz pierwszy przypadek testowy.
Alex A.
3
Ważny przypadek testowy [1,2,2,3] => 0: dwa równe elementy w tablicy, aby sprawdzić, czy kod sprawdza różnicę ( xi-xi) tylko przez porównanie z 0.
randomra
@ randomra Dziękuję, całkowicie zapomniałem dołączyć jeden z nich. Ilekroć dwa wpisy są równe, wyznacznikiem będzie 0, ponieważ są dwa razy ten sam wiersz.
flawr
1
@flawr Oczekiwany wynik był jasny z twoich specyfikacji. Zasugerowałem przypadek testowy, aby odpowiedzi nieprzygotowane na równe liczby mogły łatwiej znaleźć błędy.
randomra

Odpowiedzi:

9

Galaretka, 6 bajtów

œc2IFP

œc2pobiera wszystkie kombinacje bez zamiany długości 2. Ioblicza listę różnic dla każdej z tych par, dając listę podobną do [[1], [2], [3], ..., [1]]. Mamy FLatten i podjąć Product.

Wypróbuj tutaj!

Lynn
źródło
8

Ruby, 49 47 bajtów

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

Jest to funkcja lambda, która przyjmuje tablicę jednowymiarową o wartościach rzeczywistych i zwraca liczbę zmiennoprzecinkową lub liczbę całkowitą w zależności od typu danych wejściowych. Aby go wywołać, przypisz go do zmiennej, a następnie zrób f.call(input).

Otrzymujemy wszystkie kombinacje rozmiaru 2 używamy .combination(2)i otrzymujemy różnice dla każdej pary używającej .map {|a, b| b - a}. Łączymy wynikową tablicę w ciąg oddzielony *, a następnie evalten, który zwraca produkt. Jeśli dane wejściowe mają długość 1, będzie nilto wartość falsey w Ruby, więc możemy ||1na końcu zwrócić 1 w tej sytuacji. Zauważ, że to nadal działa, gdy produkt ma wartość 0, ponieważ z jakiegokolwiek powodu 0 jest zgodne z Ruby.

Sprawdź wszystkie przypadki testowe online

Zaoszczędzono 2 bajty dzięki Klamce!

Alex A.
źródło
7

Mathematica, 30 bajtów

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

To anonimowa funkcja.

Rozszerzony przez Mathematica jest równoważny (1 ##1 & ) @@ Apply[#2 - #1 & , Subsets[#1, {2}], {1}] &. 1##&jest odpowiednikiem Times(strona z poradami dzięki), który jest stosowany do każdej odrębnej pary elementów z listy danych wejściowych, generowanych przez Subsets[list, {2}]. Pamiętaj, że Subsetsnie sprawdza wyjątkowości elementów.

feersum
źródło
5

J, 13 bajtów

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

Jest to funkcja monadyczna, która przyjmuje tablicę i zwraca liczbę. Użyj tego w ten sposób:

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

Wyjaśnienie

Wyraźnie konstruuję macierz Vandermonde powiązaną z tablicą wejściową, a następnie obliczam jej wyznacznik.

-/ .*@(^/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
źródło
Myślałem, że białe znaki nie są kluczowe w J ...
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Wyznacznik jest szczególnym przypadkiem, który wymaga spacji oddzielającej, ponieważ .jest także znakiem modyfikującym. To samo dotyczy :samego.
Zgarb,
O! To super.
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Właściwie myślę, że właśnie to sprawia, że ​​J nie jest cool. J oznacza Jot, tj. Kropkę lub mały pierścień (APL ), jak w przypadku zapisywania za pomocą J ... Niezwykle przeciążone .i :(które znowu jest wizualnie takie samo jak dwa stosy .) sprawia, że ​​J jest trudny do odczytania (dla mnie). O ile bardziej, gdy białe spacje obok kropek określają znaczenie! J użytkownika .musi być najbardziej przeciążony symbol w całej historii obliczeniowej: Liczę 53 różnych znaczeń .i 43 (61, jeśli liczyć wszystkie _9:do 9:) różne znaczenia :. Fuj. ;-)
Adám
@ Nᴮᶻ może pomóc pomyśleć o. jako własny token; w ten sposób można bez pomyłki pomylić go z innym operatorem. Jeśli jednak J nie jest dla ciebie, jest to zrozumiałe.
Conor O'Brien
4

MATL , 9

!G-qZRQpp

Wypróbuj online!

To oblicza macierz wszystkich różnic, a następnie utrzymuje tylko część poniżej głównej przekątnej, czyniąc pozostałe wpisy, 1aby nie wpływały na produkt. Dolna trójkątna funkcja sprawia, że ​​niechciane elementy 0nie 1. Odejmujemy 1, bierzemy dolną trójkątną część i dodajemy z 1powrotem. Następnie możemy wziąć iloczyn wszystkich wpisów.

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
źródło
To niefortunne, ale 2Xn!dpwydaje się, że działa tylko z pojedynczymi wartościami, gdy wartość jest większa lub równa 2 ... Napisałem to sam, próbując pokonać Jelly: P
FryAmTheEggman
@FryAmTheEggman Awww. Masz rację. Dzięki za heads-up!
Luis Mendo,
Tak, pomyślałem, że to jest problem. Rozważę wypróbowanie czegoś takiego, jak dodanie opakowania, gdy będziesz Xnw stanie wykonać kontrolę if size(arg) == [1,1] ...lub coś w tym rodzaju. Jestem zbyt leniwy, by patrzeć przez źródło, ale (mam nadzieję) nie powinno to być takie trudne.
FryAmTheEggman
@FryAmTheEggman W rzeczywistości nie jestem pewien, czy to jest problem (dlatego szybko zredagowałem swój komentarz). Jeśli pierwszym wejściem jest liczba, to drugim wejściem powinno być 1lub 0i wtedy nie ma znaczenia, czy pierwsze wejście jest interpretowane jako tablica czy jako liczba. Prawdziwy problem polega na tym, że drugie wejście nie może przekroczyć rozmiaru tablicy. „Ile jest sposobów wyboru 2 elementów z 1 elementu”. W tym przypadku różnica między tablicą / liczbą ma znaczenie: jeśli pierwszym wejściem jest powrót do tablicy [](pusta tablica), jeśli jest to powrót liczby 0. Chyba wrócę [], bo wtedy pwymusza drugą interpretację
Luis Mendo
@FryAmTheEggman Myślę, że podzielę funkcję na dwie wersje. Dzięki jeszcze raz!
Luis Mendo,
3

Pyth, 15 13 12 11 bajtów

*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)

Dzięki @FryAmTheEggman i @ Pietu1998 za bajt każdy!

Klamka
źródło
1
* F na pustej tablicy powinno naprawdę wynosić 1.
lirtosiast
3

Mathematica, 32 bajty

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

Byłem zaskoczony, że nie znalazłem wbudowanego w Vandermonde. Prawdopodobnie dlatego, że tak łatwo to zrobić samemu.

Ta jednoznacznie konstruuje transpozycję VM i przyjmuje jej wyznacznik (który jest oczywiście taki sam jak oryginał). Ta metoda okazała się znacznie krótsza niż przy użyciu jakiejkolwiek znanej mi formuły.

hYPotenuser
źródło
3

Haskell, 34 bajty

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

Rozwiązanie rekurencyjne. Kiedy nowy element hjest dodawany na początku, wyrażenie jest mnożone przez iloczyn x-hkażdego z elementów xlisty. Dzięki Zgarb za 1 bajt.

xnor
źródło
2

Matlab, 26 bajtów

(niekonkurencyjny)

Proste użycie wbudowanych funkcji. Zauważ, że (jeszcze raz) Matlab vandertworzy macierze Vandermonde, ale z odwróconą kolejnością wierszy.

@(v)det(fliplr(vander(v)))
wada
źródło
2
Dlaczego niekonkurować?
Alex A.
3
Ponieważ to ja podjąłem to wyzwanie, chciałem tylko to zapewnić, aby ludzie mogli wypróbować własne przykłady.
flawr
Czy Det (odwrócone wiersze) = (-1) ^ n Det (oryginał)?
hYPotenuser
Nie jestem do końca pewien, ponieważ przełączniki determinujące podpisują się przy każdej zmianie dwóch kolumn lub wierszy.
flawr
@hYPotenuser - Zamień n na n + 1. Wszystko, co robisz, to mnożenie przez macierz P, która jest zerami, z wyjątkiem przekątnej przechodzącej od lewego dolnego rogu do prawego górnego rogu (więc chcesz det (P * vander (v)) = det (P) det (vander (v ))). Po rozwinięciu wzdłuż pierwszej kolumny lub cokolwiek, zobaczysz det (P) = (-1) ^ (n + 1).
Batman
2

Rdza, 86 bajtów

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

Rdza, jak zwykle verbose ...

Wyjaśnienia nadejdą później (choć jest to dość proste).

Klamka
źródło
2

Perl, 38 41 bajtów

Uwzględnij +1 dla -p

Podaj liczby w wierszu na STDIN. Więc np. Uruchom jako

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

Użyj wyrażenia regularnego zła, aby uzyskać podwójną pętlę:

vandermonde.pl:

$n=1;/(^| ).* (??{$n*=$'-$&;A})/;*_=n
Ton Hospel
źródło
2

JavaScript (ES6), 61 bajtów

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

Próbowałem zrozumieć tablicę (Firefox 30-57) i było to o 5 bajtów dłużej:

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

Nudna zagnieżdżona pętla jest jednak prawdopodobnie krótsza.

Neil
źródło
1

Haskell, 53 bajty

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

Przykład użycia: f [1,2,4,8,16]-> 20321280.

Przejdź przez indeksy ji izagnieżdżoną pętlę i zrób listę różnic między elementami w pozycji ji i. Zrób iloczyn wszystkich elementów z listy.

Inne warianty, które okazały się nieco dłuższe:

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

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

nimi
źródło
1

CJam, 16 bajtów

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

W odpowiedzi na post A Simmonsa , pomimo braku operatora kombinacji CJama, tak, można zrobić lepiej :)

-1 bajt dzięki @ MartinBüttner.

Wypróbuj online | Zestaw testowy

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
źródło
0

CJam, 32 bajty

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

Jestem pewien, że ktoś może lepiej zagrać w golfa w CJam ... Głównym problemem jest to, że nie widzę dobrego sposobu na uzyskanie podzbiorów, który zużywa większość moich bajtów. To generuje zestaw mocy (według pomysłu Martina Büttnera), a następnie wybiera elementy długości 2.

Simmons
źródło
0

R , 41 bajtów

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

Wypróbuj online!

Byłem zaskoczony, że nie widziałem tutaj odpowiedzi R.

Giuseppe
źródło