Simpson diversity index

Question

The Simpson index is a measure of diversity of a collection of items with duplicates. It is simply the probability of drawing two different items when picking without replacement uniformly at random.

With n items in groups of n_1, ..., n_k identical items, the probability of two different items is

For example, if you have 3 apples, 2 bananas, and 1 carrot, the diversity index is

D = 1 - (6 + 2 + 0)/30 = 0.7333

Alternatively, the number of unordered pairs of different items is 3*2 + 3*1 + 2*1 = 11 out of 15 pairs overall, and 11/15 = 0.7333.

Input:

A string of characters A to Z. Or, a list of such characters. Its length will be at least 2. You may not assume it to be sorted.

Output:

The Simpson diversity index of characters in that string, i.e., the probability that two characters taken randomly with replacement are different. This is a number between 0 and 1 inclusive.

When outputting a float, display at least 4 digits, though terminating exact outputs like 1 or 1.0 or 0.375 are OK.

You may not use built-ins that specifically compute diversity indices or entropy measures. Actual random sampling is fine, as long as you get sufficient accuracy on the test cases.

Test cases

AAABBC 0.73333
ACBABA 0.73333
WWW 0.0
CODE 1.0
PROGRAMMING 0.94545

Leaderboard

Here's a by-language leaderboard, courtesy of Martin Büttner.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/53455/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;var n=e.body_markdown.split("\n");try{t|=/^#/.test(e.body_markdown);t|=["-","="].indexOf(n[1][0])>-1;t&=LANGUAGE_REG.test(e.body_markdown)}catch(r){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading);answers.sort(function(e,t){var n=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0],r=+(t.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0];return n-r});var e={};var t=1;answers.forEach(function(n){var r=n.body_markdown.split("\n")[0];var i=$("#answer-template").html();var s=r.match(NUMBER_REG)[0];var o=(r.match(SIZE_REG)||[0])[0];var u=r.match(LANGUAGE_REG)[1];var a=getAuthorName(n);i=i.replace("{{PLACE}}",t++ +".").replace("{{NAME}}",a).replace("{{LANGUAGE}}",u).replace("{{SIZE}}",o).replace("{{LINK}}",n.share_link);i=$(i);$("#answers").append(i);e[u]=e[u]||{lang:u,user:a,size:o,link:n.share_link}});var n=[];for(var r in e)if(e.hasOwnProperty(r))n.push(e[r]);n.sort(function(e,t){if(e.lang>t.lang)return 1;if(e.lang<t.lang)return-1;return 0});for(var i=0;i<n.length;++i){var s=$("#language-template").html();var r=n[i];s=s.replace("{{LANGUAGE}}",r.lang).replace("{{NAME}}",r.user).replace("{{SIZE}}",r.size).replace("{{LINK}}",r.link);s=$(s);$("#languages").append(s)}}var QUESTION_ID=45497;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:&lt;(?:s&gt;[^&]*&lt;\/s&gt;|[^&]+&gt;)[^\d&]*)*$)/;var NUMBER_REG=/\d+/;var LANGUAGE_REG=/^#*\s*((?:[^,\s]|\s+[^-,\s])*)/

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><link rel=stylesheet type=text/css href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id=answer-list><h2>Leaderboard</h2><table class=answer-list><thead><tr><td></td><td>Author<td>Language<td>Size<tbody id=answers></table></div><div id=language-list><h2>Winners by Language</h2><table class=language-list><thead><tr><td>Language<td>User<td>Score<tbody id=languages></table></div><table style=display:none><tbody id=answer-template><tr><td>{{PLACE}}</td><td>{{NAME}}<td>{{LANGUAGE}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table><table style=display:none><tbody id=language-template><tr><td>{{LANGUAGE}}<td>{{NAME}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table>

Answer 1

Python 2, 72

The input may be a string or a list.

def f(s):l=len(s);return sum(s[i%l]<>s[i/l]for i in range(l*l))/(l-1.)/l

I already know that it would be 2 bytes shorter in Python 3 so please don't advise me :)

Answer 2

J, 26 bytes

1-+/((#&:>@</.~)%&(<:*])#)

the cool part

I found the counts of each character by keying </. the string against itself (~ for reflexive) then counting the letters of each box.

Answer 3

Pyth - 19 13 12 11 bytes

Thanks to @isaacg for telling me about n

Uses brute force approach with .c combinations function.

csnMK.cz2lK

Try it here online.

Test suite.

c                Float division
 s               Sum (works with True and False)
  nM             Map uniqueness
   K             Assign value to K and use value
    .c 2         Combinations of length 2
      z          Of input
 lK              Length of K

Answer 4

SQL (PostgreSQL), 182 Bytes

As a function in postgres.

CREATE FUNCTION F(TEXT)RETURNS NUMERIC AS'SELECT 1-sum(d*(d-1))/(sum(d)*(sum(d)-1))FROM(SELECT COUNT(*)d FROM(SELECT*FROM regexp_split_to_table($1,''''))I(S)GROUP BY S)A'LANGUAGE SQL

Explanation

CREATE FUNCTION F(TEXT) -- Create function f taking text parameter
RETURNS NUMERIC         -- declare return type
AS'                     -- return definition
    SELECT 1-sum(d*(d-1))/(sum(d)*(sum(d)-1)) -- Calculate simpson index
    FROM(
        SELECT COUNT(*)d  -- Count occurrences of each character
        FROM(             -- Split the string into characters
            SELECT*FROM regexp_split_to_table($1,'''')
            )I(S)
        GROUP BY S        -- group on the characters
        )A 
'
LANGUAGE SQL

Usage and Test Run

SELECT S, F(S)
FROM (
    VALUES
    ('AAABBC'),
    ('ACBABA'),
    ('WWW'),
    ('CODE'),
    ('PROGRAMMING')
   )I(S)

S              F
-------------- -----------------------
AAABBC         0.73333333333333333333
ACBABA         0.73333333333333333333
WWW            0.00000000000000000000
CODE           1.00000000000000000000
PROGRAMMING    0.94545454545454545455

Answer 5

Python 3, 66 58 Bytes

This is using the simple counting formula provided in the question, nothing too complicated. It's an anonymous lambda function, so to use it, you need to give it a name.

Saved 8 bytes(!) thanks to Sp3000.

lambda s:1-sum(x-1for x in map(s.count,s))/len(s)/~-len(s)

Usage:

>>> f=lambda s:1-sum(x-1for x in map(s.count,s))/len(s)/~-len(s)
>>> f("PROGRAMMING")
0.945454

or

>>> (lambda s:1-sum(x-1for x in map(s.count,s))/len(s)/~-len(s))("PROGRAMMING")
0.945454

Answer 6

Javascript, 119 bytes

Today on "Komali sucks at code golf"...

s=>eval('q=[];for(i of new Set(s))q.push((r=s.split(i).length-1)*(r-1));1-(q.reduce((z,x)=>x+z)/((l=s.length)*(l-1)))')

Test cases:

let s1= "AAABBC"
let s2 = "ACBABA"
let s3 = "WWW";
let s4 = "CODE";
let s5 = "PROGRAMMING"
let f = 
s=>eval('q=[];for(i of new Set(s))q.push((r=s.split(i).length-1)*(r-1));1-(q.reduce((z,x)=>x+z)/((l=s.length)*(l-1)))')

console.log(f(s1))
console.log(f(s2))
console.log(f(s3))
console.log(f(s4))
console.log(f(s5))

Came across this question while doing biology homework. There has to be ways to improve this; I only spent like half an hour golfing it...

Answer 7

APL, 39 36 bytes

{n←{≢⍵}⌸⍵⋄N←≢⍵⋄1-(N-⍨N×N)÷⍨+/n-⍨n×n}

This creates an unnamed monad.

{
  n ← {≢⍵}⌸⍵               ⍝ Number of occurrences of each letter
  N ← ≢⍵                   ⍝ Number of characters in the input
  1-(N-⍨N×N)÷⍨+/n-⍨n×n     ⍝ Return 1 - sum((n*n-n)/(N*N-N))
}

You can try it online!

Answer 8

Python 3, 56

lambda s:sum(a!=b for a in s for b in s)/len(s)/~-len(s)

Counts the pairs of unequal elements, then divides by the number of such pairs.

Answer 9

Pyth, 13 bytes

csnM*zz*lztlz

Pretty much a literal translation of @feersum's solution.

Answer 10

CJam, 25 bytes

l$_e`0f=_:(.*:+\,_(*d/1\-

Try it online

Fairly direct implementation of the formula in the question.

Explanation:

l     Get input.
$     Sort it.
_     Copy for evaluation of denominator towards the end.
e`    Run-length encoding of string.
0f=   Map letter/length pairs from RLE to only length.
      We now have a list of letter counts.
_     Copy list.
:(    Map with decrement operator. Copy now contains letter counts minus 1.
.*    Vectorized multiply. Results in list of n*(n-1) for each letter.
:+    Sum vector. This is the numerator.
\     Bring copy of input string to top.
,     Calculate length.
_(    Copy and decrement.
*     Multiply. This is the denominator, n*(n-1) for the entire string.
d     Convert to double, otherwise we would get integer division.
/     Divide.
1\-   Calculate one minus result of division to get final result.

Answer 11

K (ngn/k), 30 bytes

{1-+//((x=\:x)-=l)%(l-1)*l:#x}

33 bytes if you want it to be faster:

{1-(+/j x)%(j:{x*x-1})[+/x]}@#'=:

This is the part where not having combinators hurt k's expressiveness. Also the problem statement is wrong: the equation corresponds to taking elements without replacement.

Try it online!

Answer 12

JavaScript, 105 bytes

f=(r,f=[],n=0,a=0)=>{for(k in [...r].map(k=>f[k]=(f[k]||0)+ ++n/n),f)a+=f[k]*(f[k]-1);return 1-a/(n*n-n)}

Answer 13

JavaScript (Node.js), 81 bytes

s=>s.map(t=>s[t]=-~s[t])&&s.map(x=>(n++,a=s[x],s[x]=0,q+=a--*a),n=q=0)&&1-q/n--/n

Try it online!

Magic

The first part defines letters as keys of s by abusing that the default key is undefined, and -~undefined = 1. Then, we iteratively delete the dictionary entries after using them (the first time we encounter them) while incrementing n to count the length. Finally, we compute 1-q/n--/n.

Answer 14

J, 37 bytes

(1-([:+/]*<:)%+/*[:<:+/)([:+/"1~.=/])

but I believe it can be still shortened.

Example

(1-([:+/]*<:)%+/*[:<:+/)([:+/"1~.=/]) 'AAABBC'

This is just a tacit version of the following function:

   fun =: 3 : 0
a1=.+/"1 (~.y)=/y
N=.(+/a1)*(<:+/a1)
n=.a1*a1-1
1-(+/n)%N
)

Answer 15

C,89

Score is for the function f only and excludes unnecessary whitespace, which is only included for clarity. the main function is only for testing.

i,c,n;
float f(char*v){
  n=strlen(v);
  for(i=n*n;i--;)c+=v[i%n]!=v[i/n]; 
  return 1.0*c/(n*n-n);
}

main(int C,char**V){
  printf("%f",f(V[1]));
}

It simply compares every character with every other character, then divides by the total number of comparisons.

Answer 16

CJam, 23 bytes

1r$e`{0=,~}%_:+\,,:+d/-

Byte-wise, this is a very minor improvement over @RetoKoradi's answer, but it uses a neat trick:

The sum of the first n non-negative integers equals n(n - 1)/2, which we can use to calculate the numerator and denominator, both divided by 2, of the fraction in the question's formula.

Try it online in the CJam interpreter.

How it works

 r$                     e# Read a token from STDIN and sort it.
   e`                   e# Perform run-length encoding.
     {    }%            e# For each [length character] pair:
      0=                e#   Retrieve the length of the run (L).
        ,~              e#   Push 0 1 2 ... L-1.
                        e# Collect all results in an array.
            _:+         e# Push the sum of the entries of a copy.
               \,       e# Push the length of the array (L).
                 ,:+    e# Push 0 + 1 + 2 + ... + L-1 = L(L-1)/2.
                    d/  e# Cast to Double and divide.
1                     - e# Subtract the result from 1.

Answer 17

Haskell, 83 bytes

I know I'm late, found this, had forgotten to post. Kinda inelegant with Haskell requiring me to convert integers to numbers that you can divide by each other.

s z=(l(filter id p)-l z)/(l p-l z) where p=[c==d|c<-z,d<-z]
l=fromIntegral.length

Answer 18

APL, 26 bytes

{1-+/÷/{⍵×⍵-1}({⍴⍵}⌸⍵),≢⍵}

Explanation:

• ≢⍵: get the length of the first dimension of ⍵. Given that ⍵ is supposed to be a string, this means the length of the string.
• {⍴⍵}⌸⍵: for each unique element in ⍵, get the lengths of each dimension of the list of occurrences. This gives the amount of times an item occurs for each item, as a 1×≢⍵ matrix.
• ,: concatenate the two along the horizontal axis. Since ≢⍵ is a scalar, and the other value is a column, we get a 2×≢⍵ matrix where the first column has the amount of times an item occurs for each item, and the second column has the total amount of items.
• {⍵×⍵-1}: for each cell in the matrix, calculate N(N-1).
• ÷/: reduce rows by division. This divides the value for each item by the value for the total.
• +/: sum the result for each row.
• 1-: subtract it from 1

Answer 19

Excel, 67 bytes

=LET(n,COUNTA(A:A),c,COUNTIF(A:A,UNIQUE(A:A)),1-SUM(c^2-c)/(n^2-n))

Input is a list of characters in the column A. One character per cell. Output is wherever the formula is which can be anywhere except in column A.

The LET() function allows you to define variables that can be referenced later and it saves most of the bytes here. The arguments are in pairs of variable,value except for the last argument which is not in a pair and is instead the output.

• n,COUNTA(A:A) stores the count of how many non-blank cells there are in column A.
• c,COUNTIF(A:A,UNIQUE(A:A)) creates an array of all the unique items from column A and then counts how many times each of those unique values appear. Technically, the UNIQUE() array will include a 0 at the end (presuming there are blank cells in A:A) but COUNTIF() will return 0 for it's count so that doesn't impact the calculations.
• 1-SUM(c^2-c)/(n^2-n) is the final output. Except for turning a(a-1) into a^2-a to save a byte, then is a straightforward implementation of the formula. The denominator could have also been /n/(n-1) for the same byte count but I chose the more aesthetically pleasing option.

Answer 20

PHP 4 (72 chars)

Given $argv[1] as a command line argument :

foreach(count_chars($argv[1])as$c)@$r-=$c*$c+$g-$g+=$c;echo$r/$g/--$g+1;

Try it Online

Answer 21

TI-Basic, 75 bytes

seq(inString(Ans,sub(Ans,I,1)),I,1,length(Ans→A
SortA(ʟA
augment({0},1 and ΔList(ʟA
seq(sum(cumSum(Ans)=I),I,0,sum(Ans
1-sum(Ans²-Ans)/(sum(Ans)²-sum(Ans

Takes input in Ans as a string. Output is stored in Ans and is displayed.

Answer 22

Octave, 31 bytes

A port of xnor's Python answer.

@(s)nnz(s!=s')/(l=nnz(s))/(l-1)

Try it online!

Answer 23

K (ngn/k), 24 23 bytes

{1-/%/{x*x-1}(#'=x;#x)}

Try it online!

An adaption of @marinus' APL answer.

• (#'=x;#x) create a two item list containing: a dictionary mapping each distinct character to the number of times it appears in the input; and the length of the input string
• {x*x-1} multiply each value in the above list by itself minus one
• %/ divide the (adjusted) counts of characters by the (adjusted) length of the input
• 1-/ use a minus-reduce, seeded with 1, subtracting each of the above to (implicitly) return the metric

Answer 24

JavaScript, 100 bytes

a=>(n=a.length,1-[...new Set(a)].map(b=>((c=a.split(b).length-1)-1)*c).reduce((a,b)=>a+b)/(n*(n-1)))

Answer 25

JavaScript, 96 bytes

a=>eval('h=0,c=0,o=[];for(i of a)o[i]=o[i]+1||1,c++;for(i in o)h+=(v=o[i])*(v-1);1-h/(c*(c-1))')

Posted this as a seperate answer since it's not an update to my older one.

Answer 26

Pyt, 16 bytes

ĐĐỤ⇹ɔ⁻△Ʃ⇹Ł⁻△ᵮ/⁻~

Try it online!

Takes a list of characters

ĐĐ                    implicit input; Đuplicates on the stack twice
  Ụ                   get Ụnique elements
   ⇹ɔ                 get ɔount of each unique element in original list
     ⁻△               decrement count and get the corresponding triangular number n*(n-1)
       Ʃ              sum the triangular numbers
        ⇹Ł            get Łength of original list
          ⁻△          decrement and get triangular number
            ᵮ/        divide (cast to ᵮloat first due to bug in division coding)
              ⁻~      subtract one and negate (equivalent to subtracting from one)
                      implicit print