17
\$\begingroup\$

The Jaccard index / similarity coefficient, also known as the Tanimoto index / coefficient, is a statistic used for gauging the similarity and diversity of finite sample sets. It was developed by Grove Karl Gilbert in 1884 for the field of weather forecasting [1] and later independently developed by Paul Jaccard [2] who was studying species of alpine plants. Finally, it was also formulated again by T. Tanimoto [3]. Overall, it is widely used in various fields where binary or binarized data are used. These include computer science, ecology, genomics, etc.

Mathematically speaking, it is defined as the size of the intersection divided by the size of the union of finite sample sets. Specifically, for two sets \$A\$ and \$B\$ it is defined as:

\$J(A, B) = \frac{|A \bigcap B|}{|A\bigcup B|}\$

It ranges from \$0<= J(A, B) <=1\$, where 0 is the case of the intersection between \$A\$ and \$B\$ being equal to the empty set.

Challenge

Given two finite sets, containing positive or negative integers, calculate their Jaccard index. You may assume that at least one of the sets will be non-empty. This index is applied on mathematical sets, meaning that if your language of choice does not support sets, use any other data collection containing unique elements.

Test cases

{1, 2}, {}                -> 0.0
{-7, 3, -9}, {9, 2, 3, 4} -> ~0.167
{1, 2, 3}, {2, 4, 6}      -> 0.2
{0, 64}, {0, 64, 89, 93}  -> 0.5
{6, 42, 7, 1}, {42, 7, 6} -> 0.75
{3, 6, 9}, {3, 6, 9}      -> 1.0

Rules

\$\endgroup\$
2
  • 5
    \$\begingroup\$ I was about to comment that taking multiple inputs as a list instead of as separate inputs to the program/function is allowed under standard IO rules, but it turns out that it's not actually listed as a standard IO rule... It's certainly a de facto standard rule though \$\endgroup\$
    – pxeger
    Apr 9, 2023 at 16:55
  • 5
    \$\begingroup\$ Please vote wether allowing to take multiple inputs as a list should be standard \$\endgroup\$
    – Luis Mendo
    Apr 10, 2023 at 19:31

35 Answers 35

10
\$\begingroup\$

APL(Dyalog Unicode), 5 bytes SBCS

∩÷⍥≢∪

Try it on APLgolf!

Input A f B

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

MATL, 7 bytes

h8#uqYm

Try it at MATL online! Or verify all test cases.

How it works

h     % Implicit inputs. Concatenate
8#u   % Number of occurrences of each unique value (will be 1 or 2)
q     % Subtract 1, element-wise
Ym    % Mean. Implicit display
\$\endgroup\$
0
6
\$\begingroup\$

Vyxal, 8 7 6 bytes

₍↔∪@÷/

Try it Online!

-1 thanks to TheThonnu, -1 thanks to Lyxal

₍↔∪@÷/  # implicit input of two lists
₍       # apply each to the stack, and wrap:
 ↔      #   intersection
  ∪     #   union
   @    # map each set to its size
    ÷   # dump list onto stack
     /  # divide
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Exactly what I was about to post... \$\endgroup\$
    – The Thonnu
    Apr 9, 2023 at 16:30
  • 3
    \$\begingroup\$ 7 bytes \$\endgroup\$
    – The Thonnu
    Apr 9, 2023 at 17:29
  • 3
    \$\begingroup\$ Does this work for 6 bytes? \$\endgroup\$
    – lyxal
    Apr 10, 2023 at 6:04
5
\$\begingroup\$

Python 3, 28 bytes

lambda a,b:len(a&b)/len(a|b)

Try it online!

Simply uses the built-in python set operations

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

J, 15 12 bytes

+/@e.%#@~.@,

Uses formal definition. -3 thanks to att.

Attempt This Online!

+/@e.%#@~.@,
           ,  NB. concat
        ~.@   NB. then uniquify
      #@      NB. then get size
   e.         NB. vectorized "is x in y"
+/@           NB. then sum the resulting boolean list to get size
     %        NB. division
\$\endgroup\$
2
  • \$\begingroup\$ +/@e. on the left for -3 \$\endgroup\$
    – att
    Apr 10, 2023 at 5:51
  • \$\begingroup\$ Very clever catch. \$\endgroup\$
    – south
    Apr 10, 2023 at 14:55
4
\$\begingroup\$

K (ngn/k), 16 13 bytes

-3 from @ovs's improvement

+/%/#:\2=#'=,

Try it online!

  • =, group the concatenated inputs
  • 2= determine which elements in each input are present in both (1 if so, 0 otherwise)
  • +/%/#:\ calculate the average
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think %/|#'1&:\2=#'=, works for 15. Or I suppose your alternative could save a byte with #'1_' -> 2=#' \$\endgroup\$
    – ovs
    Apr 9, 2023 at 21:45
  • 1
    \$\begingroup\$ 13: +/%/#:\2=#'=, \$\endgroup\$
    – ovs
    Apr 9, 2023 at 21:50
  • \$\begingroup\$ Nice! I like how the #:\ (count-coverge) works here because the count of an atom is 1, thus not affecting the division-reduce that follows. \$\endgroup\$
    – coltim
    Apr 9, 2023 at 23:10
4
\$\begingroup\$

Arturo, 40 35 bytes

$[a b]->//size a--a--b size b++a--b

Try it

Port of Neil's Charcoal answer.

-- is set difference, ++ is concatenation, size is length, and // is float division.

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

Wolfram Language (Mathematica), 50 30 bytes

Tr[1^(#⋂#2)]/Tr[1^(#⋃#2)]&

Try it online!

-20 thanks to @att

\$\endgroup\$
1
  • 1
    \$\begingroup\$ -a bit \$\endgroup\$
    – att
    Apr 9, 2023 at 20:03
4
\$\begingroup\$

R, 27 bytes

\(x,y)mean(table(c(x,y))-1)

Attempt This Online!

\$\endgroup\$
1
  • \$\begingroup\$ Very nice use of non-uniqueness-enforcing containers to solve a problem of sets! \$\endgroup\$
    – Cong Chen
    Apr 11, 2023 at 11:33
4
\$\begingroup\$

Julia, 26 characters, 30 bytes

Correction from Ashlin Harris much appreciated.

n=length
A\B=n(A∩B)/n(A∪B)

Doesn't actually require A and B to be Set objects, as if they aren't it converts them anyway.

\$\endgroup\$
3
  • 7
    \$\begingroup\$ This solution is 22 characters, or 26 bytes. Also, the general consensus is to post standalone code (yours assumes values for A and B). Here's an adaptation of your solution with a test set. \$\endgroup\$ Apr 10, 2023 at 21:11
  • \$\begingroup\$ Thank you for your comment. In my rush of how boring the solution I found was I overlooked the assumed values part. Is there an easy way to see how many bytes vs characters a solution has or is tio.run the simplest? \$\endgroup\$ Apr 11, 2023 at 11:37
  • 1
    \$\begingroup\$ @JacobusSmit you could use TIO, or you could use something like this (both will do basically the same thing). \$\endgroup\$
    – The Thonnu
    Apr 11, 2023 at 11:44
3
\$\begingroup\$

05AB1E, 8 bytes

Ãg¹²«Ùg/

Try it online!

Explanation

Ãg¹²«Ùg/  # Implicit input
 g        # Length of...
à        # ...intersection of inputs...
       /  # ...divided by...
      g   # ...length of...
  ¹²      # ...both inputs...
    «     # ...merged...
     Ù    # ...without duplicates
          # Implicit output
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 74 bytes

Expects two sets as (a)(b).

There's unfortunately not any union nor intersection built-in in the current ECMAScript specification. :-/

a=>b=>new Set([...a,...b]).forEach(v=>k+=a.has(v)&b.has(v,n++),n=k=0)||k/n

Try it online!

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

Charcoal, 14 bytes

I∕L⁻θ⁻θηL⁺η⁻θη

Try it online! Link is to verbose version of code. Takes input as lists which the program assumes are unique. Explanation: Charcoal doesn't have set union or intersection but it can do set difference of two set-type lists, so I have to simulate intersection with double set difference and union by concatenation of set difference.

    θ           First input
   ⁻            Set difference with
      θ         First input
     ⁻          Set difference with
       η        Second input
  L             Take the length
 ∕              Divided by
            θ   First input
           ⁻    Set difference with
             η  Second input
         ⁺      Concatenated with
          η     Second input
        L       Take the length
I               Cast to string
                Implicitly print
\$\endgroup\$
0
3
\$\begingroup\$

Nibbles, 6.5 bytes (13 nibbles)

,`&$_"/",`|$_

Outputs as a non-reduced fraction (one of the standard I/O methods, following the consensus that reducing fractions is optional unless specified).

,               # length of
 `&             # set intersection of
   $            # arg1 and
    _           # arg2;
     "/"        # the character "/";
        ,       # length of 
         `|     # set union of
           $    # arg1 and
            _   # arg2;
                # concatenated into output

enter image description here


Nibbles, 8 bytes (16 nibbles)

/*,`&$_100,`|$_

Outputs the Jaccard index truncated at two decimal places; the decimal point is omitted (so, equivalently, an integer representing 100x the Jaccard index).

/               # divide:       
  ,             #   length of
   `&           #   set intersection of
     $          #   arg1 and
      _         #   arg2
 *     100      #   multiplied by 100   
                # by:   
          ,     #   length of 
           `|   #   set union of
             $  #   arg1 and
              _ #   arg2

enter image description here

The choice of two decimal places (costing +2.5 bytes) here is arbitrary: if zero decimal places is acceptable (meaning that output can only be 1 or 0), then the same approach could be only 5.5 bytes: /,`&$_,`|$_.

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

Lua, 106 bytes

load"i=0u=0g,h=...for k in next,g do i=h[k]and i+1or i h[k]=1 end for k in next,h do u=u+1 end return i/u"

Try it online!

Takes in tables that represent sets- This page should describe how they are formatted. Ungolfed version below.

function f(g,h)
    i=0 u=0                       -- Represents size of intersection and union
    for k in next,g do            -- For each element in set g
        i=h[k]and i+1or i         -- Increment i if k is in h
        h[k]=1                    -- Add k to set h
    end 
    for k in next,h do            -- Counts elements in h (now union set)
        u=u+1
    end 
    return i/u
end
\$\endgroup\$
0
3
\$\begingroup\$

Raku, 19 characters/23 bytes

{($^a∩$^b)/($a∪$b)}

Straight out of the definition. Try it online!

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

JavaScript, 65 bytes

a=>b=>a.filter(i=>b.includes(i)).length/new Set(a.concat(b)).size

Try it online!

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

Scala, 33 bytes

(a,b)=>((a&b).size+.0)/(a|b).size

Try it online!

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

Pyt, 15 bytes

Á←ÁáĐỤ⇹ɔĐŁ⅟⇹⁻Ʃ*

Try it online!

Á                      implicit input; push contents of Árray to stack
 ←Á                    get input; push contents of Árray to stack
   á                   push contents of stack to árray
    Đ                  Đuplicate
     Ụ                 get Ụnique elements
      ⇹                swap
       ɔ               get ɔount how many times each unique element occurs in the combined list
        Đ              Đuplicate
         Ł             get Łength (size of union)
          ⅟            multiplicative inverse
           ⇹           swap
            ⁻          decrement each element
             Ʃ         sum (size of intersection)
              *        multiply
\$\endgroup\$
0
2
\$\begingroup\$

Jelly, 7 bytes

f,œ|Ẉ÷/

Try it online!

How it works

f,œ|Ẉ÷/ - Main link. Takes A on the left, B on the right
f       - Intersection of A and B
  œ|    - Set union of A and Q
 ,      - Pair
    Ẉ   - Lengths of each
      / - Reduce the length pair by:
     ÷  -   Division
\$\endgroup\$
2
\$\begingroup\$

Factor + math.unicode, 37 bytes

[ 2dup ∩ length -rot ∪ length / ]

Try it online!

           ! { 1 2 3 } { 2 4 6 }
2dup       ! { 1 2 3 } { 2 4 6 } { 1 2 3 } { 2 4 6 }
∩          ! { 1 2 3 } { 2 4 6 } { 2 }
length     ! { 1 2 3 } { 2 4 6 } 1
-rot       ! 1 { 1 2 3 } { 2 4 6 }
∪          ! 1 { 1 2 3 4 6 }
length     ! 1 5
/          ! 1/5
\$\endgroup\$
0
2
\$\begingroup\$

Pyth, 7 bytes

cl@FQls

Try it online!

Explanation

cl@FQlsQ    # implicitly add Q
            # implicitly assign Q = eval(input())
c           # float division of
 l          # length of
  @FQ       # intersection of the two elements of Q
     l      # and the length of
      sQ    # union of the two elements of Q
\$\endgroup\$
0
2
\$\begingroup\$

BQN, 10 bytes

(+´⊒÷·≠⍷)∾

Try it at BQN REPL

         ∾  # join L & R args together
(       )   # and apply this:
 +´         #   sum of 
   ⊒        #   occurrence counts of each element
            #   (zero if one instance, one if two instances)
    ÷·      #   divided by
      ≠     #   length of
       ⍷    #   deduplicated elements
\$\endgroup\$
1
  • 2
    \$\begingroup\$ /∘∊÷○≠⍷∘∾ and ∊÷○≠○/∊∘∾ give 9 \$\endgroup\$
    – att
    Apr 10, 2023 at 23:46
2
\$\begingroup\$

Haskell, 43 bytes

a%b=1/(sum(1<$a++b)/sum[1|x<-a,elem x b]-1)

Try it online!

Haskell makes an interesting language for this challenge because it lacks sets or set operations like union barring a costly import. Also, it won't take the ratio of two lengths to make a real number without a costly type conversion.

The answer uses the formula \$1/\left(\frac{\left| A \right| + \left| B \right|}{\left| A\cap B \right|} - 1 \right)\$. The inputs are lists. Lengths are computed as sum(1<$l) which converts each element to 1 then takes the sum -- unlike length, this can produce a float because Haskell typechecks the literal 1 as a float here. The sum(1<$a++b) takes the length of the concatenation of the two inputs lists, which is the sum of their lengths.

The intersection uses a list comprehension to extract all elements of a that are also in b. Two more symmetric version of this are 1 byte longer:

a%b=1/(sum(1<$a++b)/sum[1|x<-a,y<-b,x==y]-1)
a%b=1/(sum(1<$a++b)/sum[1|0<-(-)<$>a<*>b]-1)

Importing Data.List comes out longer:

53 bytes

import Data.List
a%b=sum(1<$a++b)/sum(1<$nub(a++b))-1

Try it online!

\$\endgroup\$
2
\$\begingroup\$

PowerShell Core, 49 bytes

param($a,$b)($c=$a+$b).Count/($c|sort|gu).Count-1

Try it online!

Takes two lists as parameters, returns a double or an int32.
Knowing that A and B are sets, I'm calculating the Jaccard index this way:

U = Size of the union of A and B with duplicates
D = Size of the union of A and B without duplicates
Jaccard Index = (U - D) / D
              = U / D - 1

Explanation

param($a,$b)($c=$a+$b).Count/($c|sort|gu).Count-1  # Function body
param($a,$b)                                       # Declares the two parameters $a and $b
            ($c=$a+$b)                             # Concatenates the two input lists and keep the result in $c
                      .Count                       # Gets the size of the two set's union
                              $c|sort|gu           # Finds only the unique elements in the union
                             (          ).Count    # Calculates the size of the intersection
                            /                  -1  # Divides the size of the union by the size of the unique items and subtracts one
\$\endgroup\$
0
2
\$\begingroup\$

Thunno 2, 6 bytes

çȯċḷẸ/

Attempt This Online!

Explanation

çȯċḷẸ/  # Implicit input
ç       # Apply two functions in parallel:
 ȯ      #  Set intersection
  ċ     #  Set union
   ḷ    # Length of each list
    Ẹ   # Dump onto stack
     /  # Divide
        # Implicit output
\$\endgroup\$
0
2
\$\begingroup\$

Nekomata, 4 bytes

,Ţ←µ

Attempt This Online!

A port of @Luis Mendo's MATL answer.

,     Join
 Ţ    Tally (count occurrences of each unique element)
  ←   Decrement
   µ  Mean
\$\endgroup\$
0
1
\$\begingroup\$

Excel, 72 bytes

=LET(x,VSTACK(A1#,B1#),(COUNT(x)-COUNT(UNIQUE(x,,1)))/ROWS(UNIQUE(x))/2)

where A1# and B1# are vertical spilled ranges containing the elements of each set.

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

MathGolf, 11 bytes

+h\▀£_@-²√╠

Try it online.

Explanation:

+           # Merge the two (implicit) input-lists together
 h          # Push the total length (without popping the list)
  \         # Swap so the list is at the top of the stack again
   ▀        # Uniquify it
    £       # Pop and push the length
     _      # Duplicate this union-length
      @     # Triple-swap the stack
       -    # Subtract the union-length from the total length to get the amount of
            # items that are in both input-lists
        ²√  # Convert it to a float, by taking the square-root of its square
            # (otherwise division builtins would be integer-division)
          ╠ # Divide this top float by the duplicated union-length
            # (after which the entire stack is output implicitly as result)
\$\endgroup\$
0
1
\$\begingroup\$

Go (using golang.org/x/exp/slices), 170 168 bytes

import."golang.org/x/exp/slices"
func f(a[]int,b[]int)float64{i,j:=0.,0.
for _,x:=range a{if Contains(b,x){i++}
j++}
for _,y:=range b{if!Contains(a,y){j++}}
return i/j}

Attempt This Online!

Go has literally no built-ins (including Contains) so we have to implement set union and intersection ourselves.

-2 thanks to @code

Commented

import ."golang.org/x/exp/slices"   // Import the module we need to get Contains
func f(a []int, b []int) float64 {  // Define a function, f, taking two lists of ints,
                                    // a and b, and returning a float
  i, j := 0., 0.                    // Initialise i (Intersection length) and j (Union length) to 0.0
  for _, x := range a {             // Loop through each x in a:
    if Contains(b, x) {             //  If x is in b:
      i++ }                         //   Increment i
    j++ }                           //  Increment j
  for _, y := range b {             // Loop through each y in b:
    if ! Contains (a, y) {          //  If y is not in b:
      j++ } }                       //   Increment j
  return i / j }                    // Return the Jacard index
\$\endgroup\$
2
  • \$\begingroup\$ 168 bytes simply by removing 2 redundant newlines \$\endgroup\$
    – code
    Apr 11, 2023 at 19:26
  • \$\begingroup\$ @code thanks, updated \$\endgroup\$
    – The Thonnu
    Apr 12, 2023 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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