24
\$\begingroup\$

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

$$1-\sum_{i=1}^k \frac{n_i(n_i-1)}{n(n -1)}$$

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>

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You're using the Gini-Simpson index, when a much better measure to use is the inverse Simpson index a.k.a. effective number of types. \$\endgroup\$
    – Joe Z.
    Jul 21, 2015 at 6:00
  • 3
    \$\begingroup\$ Basically 1/ instead of 1-. [amateur statistician rant hat off] \$\endgroup\$
    – Joe Z.
    Jul 21, 2015 at 6:01

25 Answers 25

5
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ What are the angle brackets <> doing at position 36? I've never seen that syntax before. \$\endgroup\$ Jul 21, 2015 at 7:09
  • \$\begingroup\$ @TuttiFruttiJacuzzi: it's a synonym for !=. \$\endgroup\$ Jul 21, 2015 at 7:35
  • 1
    \$\begingroup\$ @TuttiFruttiJacuzzi It's only python 2 unless you from __future__ import barry_as_FLUFL \$\endgroup\$
    – matsjoyce
    Jul 21, 2015 at 12:21
  • \$\begingroup\$ @Vioz- Not with the l=len(s); in there \$\endgroup\$
    – Sp3000
    Jul 21, 2015 at 13:43
  • \$\begingroup\$ @Sp3000 Right, didn't notice how many times it was used. \$\endgroup\$
    – Kade
    Jul 21, 2015 at 13:45
5
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ (#&:>@</.~) can be (#/.~) and (<:*]) can be (*<:). If you use a proper function this gives (1-(#/.~)+/@:%&(*<:)#). As the surrounding braces are generally not counted here (leaving 1-(#/.~)+/@:%&(*<:)#, the body of the function) this gives 20 bytes. \$\endgroup\$
    – randomra
    Jul 22, 2015 at 19:56
4
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ You can replace .{ with n- they're equivalent here. \$\endgroup\$
    – isaacg
    Jul 21, 2015 at 1:26
  • \$\begingroup\$ @isaacg oh didn't know it automatically splats, cool. \$\endgroup\$
    – Maltysen
    Jul 21, 2015 at 1:29
4
\$\begingroup\$

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

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

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

\$\endgroup\$
1
  • \$\begingroup\$ (r-1) ->~-r, ditto with l (you might just want a separate function that does n*n-1), q.reduce((z,x)=>x+z) -> eval(q.join`+`)` although you probably want to make q a number and add to it. \$\endgroup\$
    – emanresu A
    May 4 at 9:49
3
\$\begingroup\$

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!

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

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.

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

Pyth, 13 bytes

csnM*zz*lztlz

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

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

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

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!

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

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)}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Golf! I don't think you need the f=, so this can be two bytes shorter. \$\endgroup\$ Apr 5 at 21:49
  • 1
    \$\begingroup\$ Well done; beat me! I believe you can omit the initial braces and return if you put the whole thing in an eval. Also you can probably put the definitions for a and n outside the arguments if you do a=n=0;for(/*...*/. Regardless, very nice answer! \$\endgroup\$
    – Komali
    Apr 6 at 12:38
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Nice! Glad to see this golfed down... \$\endgroup\$
    – Komali
    May 4 at 13:13
1
\$\begingroup\$

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
)
\$\endgroup\$
2
  • \$\begingroup\$ After some extra golfing and making it a proper function: (1-(%&([:+/]*<:)+/)@(+/"1@=)) gives 29 bytes. 27 if we don't count the braces surrounding the function (1-(%&([:+/]*<:)+/)@(+/"1@=)) as it is common here. Notes: =y is exactly (~.=/])y and the compose conjuction (x u&v y = (v x) u (v y)) was very helpful too. \$\endgroup\$
    – randomra
    Jul 21, 2015 at 10:07
  • \$\begingroup\$ Thanks for the suggestions! I am still learning to write tacit expressions myself. For now, I use 13 : 0 to generate tacit definitions part by part and combine. \$\endgroup\$
    – gar
    Jul 21, 2015 at 13:14
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ at return 1.0, couldn't you golf the 0 ? \$\endgroup\$
    – user111777
    Apr 5 at 14:05
1
\$\begingroup\$

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

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

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

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.

Screenshot

\$\endgroup\$
1
  • \$\begingroup\$ =LET(n,ROWS(A1#),c,COUNTIF(A1#,UNIQUE(A1#)),1-SUM(c^2-c)/(n^2-n)) (or =LET(a,A1#,...) ) lets you drop two bytes if you specify that input must be of the form of a vertically aligned array of chars (ie [A1]=={"a";"b";"a";"a";"b";"c"}) \$\endgroup\$ Apr 8 at 4:25
1
\$\begingroup\$

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

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

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.

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

Octave, 31 bytes

A port of xnor's Python answer.

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

Try it online!

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

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

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)))
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf, and nice first answer! Glad to see the eval was able to be omitted with this strategy! \$\endgroup\$
    – Komali
    Apr 8 at 13:38
0
\$\begingroup\$

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.

\$\endgroup\$
0

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.