25
\$\begingroup\$

Given a vector of \$n\$ values \$(x_1,x_2,x_3,\ldots,x_n)\$ return the determinant of the corresponding Vandermonde matrix

\$V(x_1, x_2, \ldots, x_n) = \begin{bmatrix}1 & x_1 & x_1^2 & x_1^3 & \ldots &x_1^{n-1} \\1 & x_2 & x_2^2 & x_2^3 & \ldots &x_2^{n-1} \\ \vdots & & & \vdots & & \vdots \\ 1 & x_n & x_n^2 & x_n^3 & \ldots & x_n^{n-1}\end{bmatrix}\$.

This determinant can be written as:

\$\det V(x_1, x_2, \ldots x_n) = \prod_\limits{1 \leqslant i < j \leqslant n} (x_j - x_i)\$

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
\$\endgroup\$
5
  • \$\begingroup\$ Can we assume the input is at least of length 2? \$\endgroup\$ Mar 4 '16 at 21:00
  • \$\begingroup\$ @Pietu1998 No, see the first test case. \$\endgroup\$
    – Alex A.
    Mar 4 '16 at 21:02
  • 3
    \$\begingroup\$ Important test case: [1,2,2,3] => 0: two equal elements in the array, to test if the code checks self-difference (xi-xi) just by comparing to 0. \$\endgroup\$
    – randomra
    Mar 5 '16 at 11:10
  • \$\begingroup\$ @randomra Thank you, I totally forgot to include one of those. Whenever two entries are equal, the determinant will be 0 as there are two times the same row. \$\endgroup\$
    – flawr
    Mar 7 '16 at 20:39
  • 1
    \$\begingroup\$ @flawr The expected output was clear from your specs. I suggested the test case so answers not prepared for equal numbers could find their mistakes more easily. \$\endgroup\$
    – randomra
    Mar 7 '16 at 21:19

23 Answers 23

10
\$\begingroup\$

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!

\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$
0
7
\$\begingroup\$

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!

\$\endgroup\$
0
4
\$\begingroup\$

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
\$\endgroup\$
6
  • \$\begingroup\$ I thought whitespace was non-crucial in J... \$\endgroup\$ Mar 5 '16 at 18:02
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ The determinant is a special case that requires a separating space, since . is also a modifier character. Same for : on its own. \$\endgroup\$
    – Zgarb
    Mar 5 '16 at 18:29
  • \$\begingroup\$ Oh! That's cool. \$\endgroup\$ Mar 5 '16 at 18:30
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ Actually, I think that is exactly what makes J uncool. J stands for Jot, i.e. a dot or little ring (APL's ), as in jotting with J... The incredibly overloaded . and : (which again is visually the same as two stacked .s) makes J hard to read (for me). How much more so when whitespace next to the dots determine meaning! J's . must be the most overloaded symbol in all of computing history: I count 53 distinct meanings of . and 43 (61 if you count all of _9: to 9:) distinct meanings of :. Yukk. ;-) \$\endgroup\$
    – Adám
    Mar 7 '16 at 13:28
  • \$\begingroup\$ @Nᴮᶻ it may help to think of the . as its own token; thus, it could, without a white space, be mistaken for another operator. If J is not for you, however, that's understandable. \$\endgroup\$ Mar 7 '16 at 17:50
4
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ It's unfortunate but 2Xn!dp only seems to work with single values when the value is greater than or equal to 2... I had written it myself trying to beat Jelly :P \$\endgroup\$ Mar 4 '16 at 21:42
  • \$\begingroup\$ @FryAmTheEggman Awww. You are right. Thanks for the heads-up! \$\endgroup\$
    – Luis Mendo
    Mar 4 '16 at 21:48
  • \$\begingroup\$ Yeah, I figured that was the problem. I'd consider trying something like adding a wrapper when you get Xn to do a check like if size(arg) == [1,1] ... or something. I'm too lazy to look trough the source, but (hopefully) it shouldn't be that difficult. \$\endgroup\$ Mar 4 '16 at 21:52
  • \$\begingroup\$ @FryAmTheEggman In fact I'm not sure that's the problem (that's why I quickly edited my comment). If the first input is a number then the second input should be 1 or 0 and then it makes no difference if the first input is interpreted as array or as a number. The real problem is, second input can't exceed the array size. "How many ways are there to choose 2 elements out of 1 element". In this case the array/number difference matters: if first input is an array return [](empty array), if it's a number return 0. I guess I'll return [], because then p forces the other interpretation \$\endgroup\$
    – Luis Mendo
    Mar 4 '16 at 22:01
  • \$\begingroup\$ @FryAmTheEggman I think I'll split the function in two versions. Thanks again! \$\endgroup\$
    – Luis Mendo
    Mar 4 '16 at 22:44
3
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ *F on an empty array should really be 1. \$\endgroup\$
    – lirtosiast
    Mar 6 '16 at 16:28
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Does not work if the list contains a zero element (giving 0^0 for j=0). \$\endgroup\$
    – Roman
    Oct 7 '20 at 12:24
  • \$\begingroup\$ "I was surprised not to find a builtin for Vandermonde stuff." There is, but is somewhat hidden (and undocumented). Moreover, it does not make it shorter ;) : Det@*LinearAlgebra`Private`VandermondeMatrix. \$\endgroup\$ Oct 11 '20 at 12:33
3
\$\begingroup\$

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.

\$\endgroup\$
0
3
+200
\$\begingroup\$

APL (Dyalog Extended), 19 bytes

{×/-∊(⍳≢⍵)↓¨↓∘.-⍨⍵}

Dfn producing the pairs, then taking the product.

↓∘.-⍨⍵ all pairs (with repeats)

(⍳≢⍵) range from 1 to the length of the input

↓¨ drop 1 2 3 4... elements to avoid repeats

-∊ flatten and negate

×/ take the product

Try it online!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ ↓∘.-⍨⍵ -> ⍵-⊂⍵ and train: ×/∘∊⍳∘≢↓¨⊂-⊢ \$\endgroup\$
    – ngn
    Oct 6 '20 at 21:48
  • \$\begingroup\$ That's pretty clever, should I update my post? \$\endgroup\$
    – rak1507
    Oct 7 '20 at 9:07
  • \$\begingroup\$ thanks. sure, update and explain it if you want. i have no intention of posting separately. \$\endgroup\$
    – ngn
    Oct 7 '20 at 13:52
2
\$\begingroup\$

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)))
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Why noncompeting? \$\endgroup\$
    – Alex A.
    Mar 4 '16 at 20:35
  • 3
    \$\begingroup\$ Because I'm the one who made this challenge, I just wanted to provide this so people can try their own examples. \$\endgroup\$
    – flawr
    Mar 4 '16 at 20:36
  • \$\begingroup\$ Isn't Det(flipped rows) = (-1)^n Det(original)? \$\endgroup\$ Mar 4 '16 at 21:22
  • \$\begingroup\$ I'm not quite sure, as the determinant switches sign whenever you switch two columns or rows. \$\endgroup\$
    – flawr
    Mar 4 '16 at 22:24
  • \$\begingroup\$ @hYPotenuser - Replace n with n+1. All you're doing is multiplying by a matrix P which is all zeros except for the diagonal going from the bottom left to top right (so you want det(P * vander(v))= det(P) det(vander(v))). By expansion along the first column or whatever, you'll see det(P) = (-1)^(n+1). \$\endgroup\$
    – Batman
    Apr 24 '18 at 2:39
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 6 bytes

η-€¨˜P

Try it online!

Commented:

η         # prefixes of the input
 -        # subtract those from the input
  €       # for each sublist:
   ¨      #   remove the last element (i=j)
    ˜     # flatten the list
     P    # take the product

There are a few alternatives at the same length, such as ηõš-˜P.

\$\endgroup\$
1
\$\begingroup\$

Desmos, 10+39=49 bytes

n=a.length
\prod_{i=1}^n\prod_{j=i+1}^n(a[j]-a[i])

View it in Desmos

There's not a lot to be golfed here other than "caching" a.length in an array, but I would like to point out that Desmos can handle the ... notation in arrays!

\$\endgroup\$
1
\$\begingroup\$

Japt v1.4.5, 8 bytes

à2 ®rnÃ×

Try it (includes all test cases)

à2 ®raÃ×     :Implicit input of array
à2           :Combinations of length 2 (using v1.4.5 avoids a bug here in later versions)
   ®         :Map
    r        :  Reduce by
     n       :  Inverse subtraction
      Ã      :End map
       ×     :Reduce by multiplication
\$\endgroup\$
5
  • \$\begingroup\$ [-13513] returns -13513. \$\endgroup\$
    – Razetime
    Oct 6 '20 at 14:16
  • 2
    \$\begingroup\$ I cobbled this together based on other solutions, @Razetime, 'cause I don't "speak" mathematical notation*; other than the fact that the a should be an n, though (which wouldn't affect this test case), I can't figure out what the fix should be. The insomnia probably isn't helping. (*I really wish people would stop relying on it as the sole means of defining their spec). \$\endgroup\$
    – Shaggy
    Oct 6 '20 at 15:40
  • \$\begingroup\$ can relate very much to that. \$\endgroup\$
    – Razetime
    Oct 6 '20 at 15:41
  • \$\begingroup\$ Figured it out: Japt v1.4.6 introduced a bug whereby attempting to get the combinations of length n of an array with length less than n returns the original array instead of the empty array so I was able to "fix" it by downgrading to v1.4.5. Thanks, @Razetime \$\endgroup\$
    – Shaggy
    Oct 6 '20 at 15:55
  • \$\begingroup\$ Nice work done! +1 \$\endgroup\$
    – Razetime
    Oct 6 '20 at 15:57
1
\$\begingroup\$

Husk, 12 9 bytes

ΠΣ→½∂↔´Ṫ-

Try it online!

(Apparently the only one of the three which was correct)

-3 bytes by calculating difference instead of pairs.

Explanation

ΠΣ→½∂↔´Ṫ-
       Ṫ- cartesian difference of pairs of the array
      ´   double: f x = f x x
     ↔    reverse
    ∂     take antidiagonals
  →½      halve and take the last part (triangle) 
 Σ        concatenate into list of pairs
Π            multiply all values
\$\endgroup\$
2
  • \$\begingroup\$ @Shaggy the longest one was the correct one :P \$\endgroup\$
    – Razetime
    Oct 6 '20 at 16:02
  • \$\begingroup\$ 8 bytes through using prefixes instead \$\endgroup\$
    – Jo King
    Oct 7 '20 at 4:35
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Perl 5 -pa, 36 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Arn, 27 bytes

ùW®š¡'‡ùHÓáâ§○iò;êñ⁺bì&B"$7

Try it!

Explained

Unpacked: *{*v{v-:{}\.{}\[_ _{.{}->--((:s)#

* ... \                  % Fold with multiplication after mapping
  {                      % Begin block
    * ... \
      v{                 % Block with key of `v`
          v              % Variable with identifier `v`
        -                % Minus
            _            % Variable intialized to STDIN; implied
          :{             % Head
      }                  % End block
              _          % Implied
            .{           % Beheaded
  }
        [                % Begin sequence
          _              % Entry equal to STDIN
          _{             % Block with key of `_` (needed otherwise the first `_` will be grabbed)
              _          % Last entry; implied
            .{           % Beheaded
          }
          ->             % Of length
            --           % Reduced by one
              (          % Begin expression
                  (
                      _  % Implied
                    :s   % Split on spaces
                  )      % End expression
                #        % Length
              )          % Implied
        ]                % End of sequence; implied

Had to fix a few major bugs I only found because of this challenge! Also made me consider adding a few quality of life features (including an upgrade to precedence and # automatically casting to a vector).

Speaking of bugs, I am 100% certain this works on the downloadable version, and it should be working on the online version very soon.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.