The Indeks Simpson adalah ukuran dari keragaman koleksi item dengan duplikat. Ini hanya probabilitas menggambar dua item yang berbeda saat memilih tanpa penggantian secara acak.

Dengan nitem dalam kelompok n_1, ..., n_kitem identik, probabilitas dua item berbeda adalah

Misalnya, jika Anda memiliki 3 apel, 2 pisang, dan 1 wortel, indeks keanekaragamannya adalah

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

Atau, jumlah pasangan yang tidak berurutan dari berbagai item berbeda 3*2 + 3*1 + 2*1 = 11dari 15 pasangan secara keseluruhan, dan 11/15 = 0.7333.

Memasukkan:

String karakter Auntuk Z. Atau, daftar karakter semacam itu. Panjangnya minimal 2. Anda mungkin tidak menganggapnya disortir.

Keluaran:

Indeks keanekaragaman Simpson karakter dalam string itu, yaitu probabilitas bahwa dua karakter diambil secara acak dengan penggantian berbeda. Ini adalah angka antara 0 dan 1 inklusif.

Saat mengeluarkan float, tampilkan setidaknya 4 digit, meskipun mengakhiri output persis seperti 1atau 1.0atau 0.375OK.

Anda tidak boleh menggunakan bawaan yang secara khusus menghitung indeks keanekaragaman atau ukuran entropi. Pengambilan sampel acak yang sebenarnya baik-baik saja, selama Anda mendapatkan akurasi yang cukup pada kasus uji.

Uji kasus

AAABBC 0.73333
ACBABA 0.73333
WWW 0.0
CODE 1.0
PROGRAMMING 0.94545

Papan peringkat

Berikut adalah papan peringkat berdasarkan bahasa, milik Martin Büttner .

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

# Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

# 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

Input mungkin berupa string atau daftar.

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

Saya sudah tahu bahwa itu akan menjadi 2 byte lebih pendek di Python 3 jadi tolong jangan beri tahu saya :)

Pyth - 19 13 12 11 byte

Terima kasih kepada @isaacg karena memberi tahu saya tentang n

Menggunakan pendekatan brute force dengan .cfungsi kombinasi.

csnMK.cz2lK

Coba di sini online .

Suite uji .

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

Sebagai fungsi di 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

Penjelasan

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

Penggunaan dan Uji Coba

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 byte

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

bagian yang keren

Saya menemukan jumlah setiap karakter dengan memasukkan </.string ke dirinya sendiri ( ~untuk refleksif) kemudian menghitung huruf setiap kotak.

Python 3, 66 58 Bytes

Ini menggunakan rumus penghitungan sederhana yang disediakan dalam pertanyaan, tidak ada yang terlalu rumit. Ini adalah fungsi lambda anonim, jadi untuk menggunakannya, Anda harus memberi nama.

Disimpan 8 byte (!) Berkat Sp3000.

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

Pemakaian:

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

atau

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

APL, 39 36 byte

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

Ini menciptakan monad yang tidak disebutkan namanya.

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

Anda dapat mencobanya secara online !

Pyth, 13 byte

csnM*zz*lztlz

Cukup banyak terjemahan harfiah dari solusi @ feersum.

CJam, 25 byte

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

Cobalah online

Implementasi formula yang cukup langsung dalam pertanyaan.

Penjelasan:

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 byte

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

tapi saya yakin itu masih bisa dipersingkat.

Contoh

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

Ini hanya versi diam-diam dari fungsi berikut:

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

C, 89

Skor hanya untuk fungsi fdan tidak termasuk spasi yang tidak perlu, yang hanya termasuk untuk kejelasan. yang mainfungsi hanya untuk pengujian.

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

Ini hanya membandingkan setiap karakter dengan setiap karakter lain, kemudian membaginya dengan jumlah total perbandingan.

Python 3, 56

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

Menghitung pasangan elemen yang tidak sama, kemudian membaginya dengan jumlah pasangan tersebut.

Haskell, 83 byte

Saya tahu saya terlambat, menemukan ini, lupa memposting. Agak tidak sopan dengan Haskell yang mengharuskan saya untuk mengkonversi bilangan bulat ke angka yang dapat Anda bagi satu sama lain.

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 byte

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

Byte-wise, ini adalah peningkatan yang sangat kecil dari jawaban @ RetoKoradi , tetapi menggunakan trik yang rapi:

Jumlah dari bilangan bulat n -negatif pertama sama dengan n (n - 1) / 2 , yang dapat kita gunakan untuk menghitung pembilang dan penyebut, keduanya dibagi dengan 2 , dari fraksi dalam rumus pertanyaan.

Cobalah online di juru bahasa CJam .

Bagaimana itu bekerja

 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 byte

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

Penjelasan:

• ≢⍵: dapatkan panjang dimensi pertama ⍵. Mengingat yang ⍵seharusnya berupa string, ini berarti panjang string.
• {⍴⍵}⌸⍵: untuk setiap elemen unik ⍵, dapatkan panjang setiap dimensi dari daftar kejadian. Ini memberikan berapa kali suatu item muncul untuk setiap item, sebagai sebuah 1×≢⍵matriks.
• ,: menyatukan keduanya di sepanjang sumbu horizontal. Karena ≢⍵skalar, dan nilai lainnya adalah kolom, kita mendapatkan 2×≢⍵matriks di mana kolom pertama memiliki jumlah kali suatu item terjadi untuk setiap item, dan kolom kedua memiliki jumlah total item.
• {⍵×⍵-1}: untuk setiap sel dalam matriks, hitung N(N-1).
• ÷/: kurangi baris dengan pembagian. Ini membagi nilai untuk setiap item dengan nilai untuk total.
• +/: jumlah hasil untuk setiap baris.
• 1-: kurangi dari 1