O índice Simpson é uma medida da diversidade de uma coleção de itens com duplicatas. É simplesmente a probabilidade de desenhar dois itens diferentes ao escolher sem substituição uniforme de forma aleatória.

Com nitens em grupos de n_1, ..., n_kitens idênticos, a probabilidade de dois itens diferentes é

Por exemplo, se você tiver 3 maçãs, 2 bananas e 1 cenoura, o índice de diversidade será

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

Como alternativa, o número de pares não ordenados de itens diferentes está 3*2 + 3*1 + 2*1 = 11fora de 15 pares no total, e 11/15 = 0.7333.

Entrada:

Uma sequência de caracteres Apara Z. Ou, uma lista desses caracteres. Seu comprimento será pelo menos 2. Você não pode assumir que ele esteja classificado.

Resultado:

O índice de diversidade Simpson de caracteres nessa sequência, ou seja, a probabilidade de dois caracteres escolhidos aleatoriamente com a substituição serem diferentes. Este é um número entre 0 e 1, inclusive.

Ao emitir um flutuador, exiba pelo menos 4 dígitos, embora encerre saídas exatas como 1ou 1.0ou 0.375estão OK.

Você não pode usar built-ins que computem especificamente índices de diversidade ou medidas de entropia. A amostragem aleatória real é boa, desde que você obtenha precisão suficiente nos casos de teste.

Casos de teste

AAABBC 0.73333
ACBABA 0.73333
WWW 0.0
CODE 1.0
PROGRAMMING 0.94545

Entre os melhores

Aqui está uma tabela de classificação por idioma, cortesia de Martin Büttner .

Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

# Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

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

Python 2, 72

A entrada pode ser uma sequência ou uma lista.

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

Eu já sei que seria 2 bytes mais curto no Python 3, então por favor não me avise :)

Pitão - 19 13 12 11 bytes

Obrigado a @isaacg por me contar sobre n

Usa abordagem de força bruta com .cfunção de combinações.

csnMK.cz2lK

Experimente aqui online .

Conjunto de teste .

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

SQL (PostgreSQL), 182 bytes

Como uma função no 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

Explicação

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

Uso e execução de teste

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

J, 26 bytes

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

a parte legal

Encontrei as contagens de cada caractere pressionando </.a corda contra si mesma ( ~por reflexivo) e depois contando as letras de cada caixa.

Python 3, 66 58 bytes

Isso está usando a fórmula simples de contagem fornecida na pergunta, nada muito complicado. É uma função lambda anônima; portanto, para usá-la, você precisa dar um nome a ela.

Economizou 8 bytes (!) Graças ao Sp3000.

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

Uso:

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

ou

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

APL, 39 36 bytes

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

Isso cria uma mônada sem nome.

{
  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))
}

Você pode experimentá-lo online !

Pitão, 13 bytes

csnM*zz*lztlz

Praticamente uma tradução literal da solução do @ feersum.

CJam, 25 bytes

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

Experimente online

Implementação bastante direta da fórmula na questão.

Explicação:

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.

J, 37 bytes

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

mas acredito que ainda pode ser reduzido.

Exemplo

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

Esta é apenas uma versão tácita da seguinte função:

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

C, 89

A pontuação é apenas para a função fe exclui espaços em branco desnecessários, incluídos apenas para maior clareza. a mainfunção é apenas para teste.

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]));
}

Ele simplesmente compara todos os caracteres com outros caracteres e depois divide pelo número total de comparações.

Python 3, 56

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

Conta os pares de elementos desiguais e depois divide pelo número de tais pares.

Haskell, 83 bytes

Eu sei que estou atrasado, achei isso, tinha esquecido de postar. Meio deselegante com Haskell exigindo que eu convertesse números inteiros em números que você pode dividir um pelo outro.

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

CJam, 23 bytes

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

Byte-wise, esta é uma melhoria muito menor do que à resposta do @ RetoKoradi , mas usa um truque:

A soma dos primeiros n números inteiros não negativos é igual a n (n - 1) / 2 , que podemos usar para calcular o numerador e o denominador, ambos divididos por 2 , da fração na fórmula da pergunta.

Experimente online no intérprete CJam .

Como funciona

 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.

APL, 26 bytes

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

Explicação:

• ≢⍵: obtém o comprimento da primeira dimensão de ⍵. Dado que ⍵deveria ser uma string, isso significa o comprimento da string.
• {⍴⍵}⌸⍵: para cada elemento exclusivo de ⍵, obtenha os comprimentos de cada dimensão da lista de ocorrências. Isso fornece a quantidade de vezes que um item ocorre para cada item, como uma 1×≢⍵matriz.
• ,: concatena os dois ao longo do eixo horizontal. Desde a≢⍵ é escalar e o outro valor é uma coluna, obtemos uma 2×≢⍵matriz em que a primeira coluna tem a quantidade de vezes que um item ocorre para cada item e a segunda coluna tem a quantidade total de itens.
• {⍵×⍵-1}: para cada célula na matriz, calcule N(N-1) .
• ÷/: reduza as linhas por divisão. Isso divide o valor de cada item pelo valor do total.
• +/: soma o resultado para cada linha.
• 1-: subtraia de 1