Indeks Simpson jest miarą różnorodności kolekcją przedmiotów z duplikatów. Jest to po prostu prawdopodobieństwo losowania dwóch różnych przedmiotów podczas wybierania bez zamiany równomiernie losowo.

W przypadku nprzedmiotów w grupach n_1, ..., n_kidentycznych przedmiotów prawdopodobieństwo dwóch różnych przedmiotów wynosi

Na przykład, jeśli masz 3 jabłka, 2 banany i 1 marchewkę, wskaźnik różnorodności wynosi

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

Alternatywnie, liczba nieuporządkowanych par różnych przedmiotów wynosi 3*2 + 3*1 + 2*1 = 11ogółem z 15 par, oraz 11/15 = 0.7333.

Wejście:

Ciąg znaków Ado Z. Lub lista takich znaków. Jego długość będzie wynosić co najmniej 2. Nie możesz zakładać, że zostanie posortowana.

Wynik:

Indeks różnorodności Simpsona znaków w tym ciągu, tj. Prawdopodobieństwo, że dwa znaki wzięte losowo z zamianą są różne. Jest to liczba od 0 do 1 włącznie.

Kiedy wypisujesz liczbę zmiennoprzecinkową, wyświetl przynajmniej 4 cyfry, ale kończąc dokładne wyjścia jak 1lub 1.0lub 0.375są OK.

Nie możesz używać wbudowanych funkcji, które konkretnie obliczają wskaźniki różnorodności lub miary entropii. Rzeczywiste losowe próbkowanie jest w porządku, o ile uzyskano wystarczającą dokładność przypadków testowych.

Przypadki testowe

AAABBC 0.73333
ACBABA 0.73333
WWW 0.0
CODE 1.0
PROGRAMMING 0.94545

Tabela liderów

Oto tabela liderów według języków, dzięki uprzejmości Martina Büttnera .

Aby upewnić się, że Twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

# Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

# 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

Dane wejściowe mogą być ciągiem lub listą.

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

Wiem już, że w Pythonie 3 byłby o 2 bajty krótszy, więc proszę, nie doradzaj mi :)

Pyth - 19 13 12 11 bajtów

Dzięki @isaacg za poinformowanie mnie o n

Wykorzystuje podejście brutalnej siły z .cfunkcją kombinacji.

csnMK.cz2lK

Wypróbuj tutaj online .

Zestaw testowy .

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 bajtów

Jako funkcja w postgresie.

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

Wyjaśnienie

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

Użycie i uruchomienie testowe

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 bajtów

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

fajna część

Znalazłem liczby każdego znaku, wpisując </.ciąg znaków do siebie ( ~dla zwrotności), a następnie licząc litery każdego pola.

Python 3, 66 58 bajtów

Korzysta z prostej formuły liczenia podanej w pytaniu, nic zbyt skomplikowanego. Jest to anonimowa funkcja lambda, więc aby z niej skorzystać, musisz nadać jej nazwę.

Zaoszczędzono 8 bajtów (!) Dzięki Sp3000.

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

Stosowanie:

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

lub

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

APL, 39 36 bajtów

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

Tworzy to nienazwaną 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))
}

Możesz spróbować online !

Pyth, 13 bajtów

csnM*zz*lztlz

Prawie dosłowne tłumaczenie rozwiązania @ feersum.

CJam, 25 bajtów

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

Wypróbuj online

Dość bezpośrednie wdrożenie formuły w pytaniu.

Wyjaśnienie:

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 bajtów

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

ale wierzę, że można to jeszcze skrócić.

Przykład

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

To tylko cicha wersja następującej funkcji:

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

C, 89

Wynik jest tylko dla funkcji fi wyklucza niepotrzebne białe znaki, które są uwzględniane tylko dla przejrzystości. mainfunkcja dostępna jest tylko do testów.

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

Po prostu porównuje każdą postać z każdą inną postacią, a następnie dzieli przez całkowitą liczbę porównań.

Python 3, 56

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

Liczy pary nierównych elementów, a następnie dzieli przez liczbę takich par.

Haskell, 83 bajty

Wiem, że się spóźniłem, znalazłem to, zapomniałem opublikować. Trochę nieelegancki w stosunku do Haskella, wymagający ode mnie konwersji liczb całkowitych na liczby, które możecie podzielić przez siebie.

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 bajty

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

Bajtowo , to bardzo niewielka poprawa w stosunku do odpowiedzi @ RetoKoradi , ale używa zgrabnej sztuczki:

Suma pierwszych n nieujemnych liczb całkowitych wynosi n (n - 1) / 2 , których możemy użyć do obliczenia licznika i mianownika, oba podzielone przez 2 ułamka we wzorze pytania.

Wypróbuj online w interpretatorze CJam .

Jak to działa

 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 bajtów

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

Wyjaśnienie:

• ≢⍵: uzyskaj długość pierwszego wymiaru ⍵. Jeśli się uwzględni⍵ ma to być łańcuch, oznacza to długość łańcucha.
• {⍴⍵}⌸⍵: dla każdego unikalnego elementu w ⍵uzyskaj długości każdego wymiaru listy wystąpień. Daje to liczbę przypadków, w których element występuje dla każdego elementu, w postaci 1×≢⍵macierzy.
• ,: połącz dwa wzdłuż osi poziomej. Ponieważ ≢⍵jest skalarem, a drugą wartością jest kolumna, otrzymujemy2×≢⍵ macierz, w której pierwsza kolumna zawiera liczbę wystąpień elementu dla każdego elementu, a druga kolumna zawiera całkowitą liczbę elementów.
• {⍵×⍵-1}: dla każdej komórki w macierzy oblicz N(N-1) .
• ÷/: zmniejsz wiersze według podziału. Dzieli to wartość dla każdego elementu przez wartość sumy.
• +/: zsumuj wynik dla każdego wiersza.
• 1-: odejmij od 1