19
\$\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\$
  • \$\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 '15 at 6:00
  • 1
    \$\begingroup\$ Basically 1/ instead of 1-. [amateur statistician rant hat off] \$\endgroup\$ – Joe Z. Jul 21 '15 at 6:01

14 Answers 14

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\$
  • \$\begingroup\$ What are the angle brackets <> doing at position 36? I've never seen that syntax before. \$\endgroup\$ – ApproachingDarknessFish Jul 21 '15 at 7:09
  • \$\begingroup\$ @TuttiFruttiJacuzzi: it's a synonym for !=. \$\endgroup\$ – RemcoGerlich Jul 21 '15 at 7:35
  • 1
    \$\begingroup\$ @TuttiFruttiJacuzzi It's only python 2 unless you from __future__ import barry_as_FLUFL \$\endgroup\$ – matsjoyce Jul 21 '15 at 12:21
  • \$\begingroup\$ @Vioz- Not with the l=len(s); in there \$\endgroup\$ – Sp3000 Jul 21 '15 at 13:43
  • \$\begingroup\$ @Sp3000 Right, didn't notice how many times it was used. \$\endgroup\$ – Kade Jul 21 '15 at 13:45
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\$
  • \$\begingroup\$ You can replace .{ with n- they're equivalent here. \$\endgroup\$ – isaacg Jul 21 '15 at 1:26
  • \$\begingroup\$ @isaacg oh didn't know it automatically splats, cool. \$\endgroup\$ – Maltysen Jul 21 '15 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\$

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
    \$\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 '15 at 19:56
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\$
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\$
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\$
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\$
  • \$\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 '15 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 '15 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\$

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\$
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\$
0
\$\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\$
0
\$\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\$

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.