Determinante de Vandermonde

25

Dado un vector de nvalores (x1,x2,x3,...,xn)devuelve el determinante de la matriz de Vandermonde correspondiente .

Este determinante se puede escribir como:

fórmula

Detalles

Su programa / función tiene que aceptar una lista de números de coma flotante en cualquier formato conveniente que permita una longitud variable y generar el determinante especificado.

Puede suponer que tanto la entrada como la salida están dentro del rango de los valores que admite su idioma. Si su idioma no admite números de coma flotante, puede suponer enteros.

Algunos casos de prueba

Tenga en cuenta que siempre que haya dos entradas iguales, el determinante será 0ya que hay dos filas iguales en la matriz de Vandermonde correspondiente. Gracias a @randomra por señalar este caso de prueba perdido.

[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
falla
fuente
¿Podemos suponer que la entrada es al menos de longitud 2?
PurkkaKoodari
@ Pietu1998 No, vea el primer caso de prueba.
Alex A.
3
Caso de prueba importante [1,2,2,3] => 0: dos elementos iguales en la matriz, para comprobar si el código comprueba la diferencia propia ( xi-xi) simplemente comparándolo con 0.
randomra
@randomra Gracias, olvidé por completo incluir uno de esos. Siempre que dos entradas sean iguales, el determinante será 0 ya que hay dos veces la misma fila.
flawr
1
@flawr El resultado esperado fue claro a partir de sus especificaciones. Sugerí el caso de prueba para que las respuestas no preparadas para números iguales puedan encontrar sus errores más fácilmente.
randomra

Respuestas:

9

Jalea, 6 bytes

œc2IFP

œc2obtiene todas las combinaciones sin reemplazar la longitud 2. Icalcula la lista de diferencias de cada uno de esos pares, produciendo una lista como [[1], [2], [3], ..., [1]]. Nos Faferramos y tomamos el Producto.

Pruébalo aquí!

Lynn
fuente
8

Ruby, 49 47 bytes

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

Esta es una función lambda que acepta una matriz unidimensional de valor real y devuelve un flotante o un entero dependiendo del tipo de entrada. Para llamarlo, asígnelo a una variable y luego hagaf.call(input) .

Obtenemos todas las combinaciones de tamaño 2 usando .combination(2)y obtenemos las diferencias para cada par usando .map {|a, b| b - a}. Unimos la matriz resultante en una cadena separada por *, luego evalesto, que devuelve el producto. Si la entrada tiene longitud 1, esta será nil, que es falsey en Ruby, por lo que ||1al final podemos devolver 1 en esta situación. Tenga en cuenta que esto todavía funciona cuando el producto es 0 porque, por cualquier razón, 0 es verdadero en Ruby.

Verifique todos los casos de prueba en línea

¡Ahorré 2 bytes gracias a Doorknob!

Alex A.
fuente
7

Mathematica, 30 bytes

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

Esta es una función anónima.

Ampliado por Mathematica, es equivalente a (1 ##1 & ) @@ Apply[#2 - #1 & , Subsets[#1, {2}], {1}] &. 1##&es un equivalente para Times(página de consejos de agradecimiento), que se aplica a cada par distinto de elementos de la lista de entrada, generado por Subsets[list, {2}]. Tenga en cuenta que Subsetsno verifica la unicidad de los elementos.

Feersum
fuente
5

J, 13 bytes

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

Esta es una función monádica que toma una matriz y devuelve un número. Úselo así:

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

Explicación

Construyo explícitamente la matriz de Vandermonde asociada con la matriz de entrada, y luego calculo su 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
fuente
Pensé que el espacio en blanco no era crucial en J ...
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ El determinante es un caso especial que requiere un espacio de separación, ya .que también es un carácter modificador. Lo mismo para :por sí solo.
Zgarb
Oh! Eso es genial.
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ En realidad, creo que eso es exactamente lo que hace que J no sea genial. J significa Jot, es decir, un punto o un pequeño anillo (APL ), como al escribir con J ... El increíblemente sobrecargado .y :(que de nuevo es visualmente el mismo que dos .s apilados ) hace que J sea difícil de leer (para mí). ¡Cuánto más cuando los espacios en blanco al lado de los puntos determinan el significado! J .debe ser el símbolo más sobrecargada en toda la historia de computación: Cuento 53 de significados distintos .y 43 (61 si se cuentan todas _9:a 9:) significados distintos de :. Yukk ;-)
Adám
@ Nᴮᶻ puede ayudar pensar en el. como su propio token; por lo tanto, sin un espacio en blanco, podría confundirse con otro operador. Si J no es para ti, eso es comprensible.
Conor O'Brien
4

MATL , 9

!G-qZRQpp

Pruébalo en línea!

Esto calcula una matriz de todas las diferencias y luego mantiene solo la parte debajo de la diagonal principal, haciendo las otras entradas 1para que no afecten al producto. La función triangular inferior hace que los elementos 0no deseados , no 1. Entonces restamos 1, tomamos la parte triangular inferior y sumamos de 1nuevo. Entonces podemos tomar el producto de todas las entradas.

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
fuente
Es lamentable, pero 2Xn!dpsolo parece funcionar con valores únicos cuando el valor es mayor o igual a 2 ... Lo escribí yo mismo tratando de vencer a Jelly: P
FryAmTheEggman
@FryAmTheEggman Awww. Tienes razón. ¡Gracias por el aviso!
Luis Mendo
Sí, pensé que ese era el problema. Consideraría intentar algo como agregar un contenedor cuando puedas Xnhacer un chequeo como if size(arg) == [1,1] ...o algo así. Soy demasiado vago para mirar a través de la fuente, pero (con suerte) no debería ser tan difícil.
FryAmTheEggman
@FryAmTheEggman De hecho, no estoy seguro de que ese sea el problema (es por eso que rápidamente edité mi comentario). Si la primera entrada es un número, entonces la segunda entrada debe ser 1o 0y no hay diferencia si la primera entrada se interpreta como una matriz o como un número. El verdadero problema es que la segunda entrada no puede exceder el tamaño de la matriz. "¿Cuántas maneras hay para elegir 2 elementos de 1 elemento". En este caso, la diferencia de matriz / número es importante: si la primera entrada es un retorno de matriz[] (matriz vacía), si es una devolución de número 0. Creo que volveré [], porque luego pobliga a la otra interpretación
Luis Mendo
@FryAmTheEggman Creo que dividiré la función en dos versiones. ¡Gracias de nuevo!
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)

Gracias a @FryAmTheEggman y @ Pietu1998 por un byte cada uno.

Pomo de la puerta
fuente
1
* F en una matriz vacía realmente debería ser 1.
lirtosiast
3

Mathematica, 32 bytes

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

Me sorprendió no encontrar un lugar para las cosas de Vandermonde. Probablemente porque es muy fácil hacerlo uno mismo.

Éste construye explícitamente la transposición de una VM y toma su determinante (que, por supuesto, es el mismo que el original). Este método resultó ser significativamente más corto que el uso de cualquier fórmula que conozco.

hYPotenuser
fuente
3

Haskell, 34 bytes

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

Una solución recursiva. Cuando hse antepone un nuevo elemento al frente, la expresión se multiplica por el producto de x-hpara cada elemento xde la lista. Gracias a Zgarb por 1 byte.

xnor
fuente
2

Matlab, 26 bytes

(sin competencia)

Uso directo de los incorporados. Tenga en cuenta que (una vez más) Matlab's vandercrea matrices de Vandermonde pero con el orden de las filas invertido.

@(v)det(fliplr(vander(v)))
falla
fuente
2
¿Por qué no competir?
Alex A.
3
Debido a que fui yo quien hizo este desafío, solo quería proporcionarlo para que las personas puedan probar sus propios ejemplos.
flawr
¿No es Det (filas invertidas) = ​​(-1) ^ n Det (original)?
hYPotenuser
No estoy muy seguro, ya que los interruptores determinantes firman cada vez que cambias dos columnas o filas.
flawr
@hYPotenuser - Reemplace n con n + 1. Todo lo que está haciendo es multiplicar por una matriz P, que es todos ceros, excepto la diagonal que va desde la parte inferior izquierda a la parte superior derecha (por lo que desea det (P * vander (v)) = det (P) det (vander (v ))). Por expansión a lo largo de la primera columna o lo que sea, verá det (P) = (-1) ^ (n + 1).
Batman
2

Óxido, 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);

Óxido, detallado como siempre ...

La explicación vendrá más tarde (sin embargo, es bastante sencillo).

Pomo de la puerta
fuente
2

Perl, 38 41 bytes

Incluye +1 para -p

Dé los números en una línea en STDIN. Entonces, por ejemplo, correr como

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

Usa una expresión regular malvada para obtener el doble bucle:

vandermonde.pl:

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

JavaScript (ES6), 61 bytes

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

Probé una comprensión de matriz (Firefox 30-57) y fue 5 bytes más larga:

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

Sin embargo, el bucle anidado aburrido es probablemente más corto.

Neil
fuente
1

Haskell, 53 bytes

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

Ejemplo de uso: f [1,2,4,8,16]->20321280 .

Ir a través de los índices jy ien un bucle anidado y hacer una lista de las diferencias de los elementos en la posición jy i. Haga el producto de todos los elementos en la lista.

Otras variantes que resultaron ser un poco más largas:

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
fuente
1

CJam, 16 bytes

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

En respuesta a la publicación de A Simmons , a pesar de la falta de un operador de combinaciones de CJam, sí, es posible hacerlo mejor :)

-1 byte gracias a @ MartinBüttner.

Pruébalo en línea | Banco de pruebas

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
fuente
0

CJam, 32 bytes

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

Estoy seguro de que alguien puede jugar mejor en CJam ... El problema principal es que no puedo ver una buena manera de obtener los subconjuntos para que use la mayoría de mis bytes. Esto genera el conjunto de potencia (utilizando una idea de Martin Büttner) y luego selecciona los elementos de longitud 2.

Un simmons
fuente
0

R , 41 bytes

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

Pruébalo en línea!

¡Me sorprendió no ver una respuesta R aquí!

Giuseppe
fuente