Vandermonde Determinant

Question

Given a vector of n values (x1,x2,x3,...,xn) return the determinant of the corresponding Vandermonde matrix.

This determinant can be written as:

Details

Your program/function has to accept a list of floating point numbers in any convenient format that allows for a variable length, and output the specified determinant.

You can assume that the input as well as the output is within the range of the values your language supports. If you language does not support floating point numbers, you may assume integers.

Some test cases

Note that whenever there are two equal entries, the determinant will be 0 as there are two equal rows in the corresponding Vandermonde matrix. Thanks to @randomra for pointing out this missing testcase.

[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

Answer 1

Jelly, 6 bytes

œc2IFP

œc2 gets all combinations without replacement of length 2. I computes the difference list of each of those pairs, yielding a list like [[1], [2], [3], ..., [1]]. We Flatten and take the Product.

Try it here!

Answer 2

Ruby, 49 47 bytes

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

This is a lambda function that accepts a real valued, one-dimensional array and returns a float or an integer depending on the type of the input. To call it, assign it to a variable then do f.call(input).

We get all combinations of size 2 using .combination(2) and get the differences for each pair using .map {|a, b| b - a}. We join the resulting array into a string separated by *, then eval this, which returns the product. If the input has length 1, this will be nil, which is falsey in Ruby, so we can just ||1 at the end to return 1 in this situation. Note that this still works when the product is 0 because for whatever reason 0 is truthy in Ruby.

Verify all test cases online

Saved 2 bytes thanks to Doorknob!

Answer 3

Mathematica, 30 bytes

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

This is an anonymous function.

Expanded by Mathematica, it is equivalent to (1 ##1 & ) @@ Apply[#2 - #1 & , Subsets[#1, {2}], {1}] &. 1##& is an equivalent for Times (thanks tips page), which is applied to each distinct pair of elements from the input list, generated by Subsets[list, {2}]. Note that Subsets does not check for uniqueness of elements.

Answer 4

J, 13 bytes

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

This is a monadic function that takes in an array and returns a number. Use it like this:

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

Explanation

I explicitly construct the Vandermonde matrix associated with the input array, and then compute its determinant.

-/ .*@(^/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

Answer 5

MATL, 9

!G-qZRQpp

Try it online!

This computes a matrix of all differences and then keeps only the part below the main diagonal, making the other entries 1 so they won't affect the product. The lower triangular function makes the unwanted elements 0, not 1. So we subtract 1, take the lower triangular part, and add 1 back. Then we can take the product of all entries.

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

Answer 6

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)

Thanks to @FryAmTheEggman and @Pietu1998 for a byte each!

Answer 7

Mathematica, 32 bytes

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

I was surprised not to find a builtin for Vandermonde stuff. Probably because it's so easy to do it oneself.

This one explicitly constructs the transpose of a VM and takes its determinant (which is of course the same as the original's). This method turned out to be significantly shorter than using any formula I know of.

Answer 8

Haskell, 34 bytes

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

A recursive solution. When a new element h is prepended to the front, the expression is multiplied by the product of x-h for each element x of the list. Thanks to Zgarb for 1 byte.

Answer 9

Matlab, 26 bytes

(noncompeting)

Straightforward use of builtins. Note that (once again) Matlab's vander creates Vandermonde matrices but with the order of the rows flipped.

@(v)det(fliplr(vander(v)))

Answer 10

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, verbose as usual...

Explanation will come later (it's pretty straightforward, though).

Answer 11

JavaScript (ES6), 61 bytes

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

I tried an array comprehension (Firefox 30-57) and it was 5 bytes longer:

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

The boring nested loop is probably shorter though.

Answer 12

Perl, 38 41 bytes

Include +1 for -p

Give the numbers on a line on STDIN. So e.g. run as

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

Use an evil regex to get the double loop:

vandermonde.pl:

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

Answer 13

Haskell, 53 bytes

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

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

Go through the indices j and i in a nested loop and make a list of the differences of the elements at position j and i. Make the product of all elements in the list.

Other variants that turned out to be slightly longer:

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

Answer 14

CJam, 16 bytes

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

In response to A Simmons' post, despite CJam's lack of a combinations operator, yes it is possible to do better :)

-1 byte thanks to @MartinBüttner.

Try it online | Test suite

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

Answer 15

R, 41 bytes

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

Try it online!

I was surprised not to see an R answer here!

Answer 16

Perl 5 -pa, 36 bytes

$\=1;map$\*=$q-$_,@F while$q=pop@F}{

Try it online!

Answer 17

CJam, 32 bytes

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

I'm sure someone can golf this better in CJam... The main issue is that I can't see a good way of getting the subsets so that uses up most of my bytes. This generates the power set (using an idea by Martin Büttner) and then selects the length-2 elements.