Индекс Симпсона является мерой разнообразия коллекции предметов с дубликатами. Это просто вероятность нарисовать два разных предмета при случайном выборе без замены.

С nпредметами в группах n_1, ..., n_kодинаковых предметов, вероятность двух разных предметов

Например, если у вас есть 3 яблока, 2 банана и 1 морковь, индекс разнообразия

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

В качестве альтернативы, количество неупорядоченных пар различных элементов 3*2 + 3*1 + 2*1 = 11в общем из 15 пар, и 11/15 = 0.7333.

Входные данные:

Строка символов Aдля Z. Или список таких персонажей. Его длина будет как минимум 2. Вы не можете предполагать, что он отсортирован.

Выход:

Индекс разнообразия Симпсона символов в этой строке, т. Е. Вероятность того, что два символа, взятых случайным образом с заменой, различны. Это число от 0 до 1 включительно.

При выводе числа с плавающей запятой отображать не менее 4 цифр, хотя точные выводы выводятся как 1или, 1.0или 0.375все в порядке.

Вы не можете использовать встроенные модули, которые специально вычисляют индексы разнообразия или меры энтропии. Фактическая случайная выборка - это хорошо, если вы получаете достаточную точность в тестовых примерах.

Контрольные примеры

AAABBC 0.73333
ACBABA 0.73333
WWW 0.0
CODE 1.0
PROGRAMMING 0.94545

Leaderboard

Вот список лидеров по языкам, любезно предоставленный Мартином Бюттнером .

Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:

# Language Name, N bytes

где Nразмер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

# 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

Входные данные могут быть строкой или списком.

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

Я уже знаю, что в Python 3 это будет на 2 байта короче, поэтому, пожалуйста, не советуйте мне :)

Pyth - 19 13 12 11 байт

Спасибо @isaacg за рассказ о

Использование грубой силы подход с .cфункцией комбинации.

csnMK.cz2lK

Попробуйте здесь онлайн .

Набор тестов .

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 байт

Как функция в 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

объяснение

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

Использование и тестовый прогон

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 байт

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

прохладная часть

Я нашел количество каждого символа, набрав </.строку против себя ( ~для отражения), а затем посчитав буквы каждого ящика.

Python 3, 66 58 байт

Это используя формулу простого подсчета, приведенную в вопросе, ничего слишком сложное нет. Это анонимная функция лямбды, поэтому использовать его, вы должны дать ему имя.

Сохранено 8 байт (!) Благодаря Sp3000.

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

Использование:

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

или

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

APL, 39 36 байт

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

Это создает безымянную монаду.

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

Вы можете попробовать его в Интернете !

Pyth, 13 байт

csnM*zz*lztlz

Практически буквальный перевод решения @ feersum.

CJam, 25 байт

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

Попробуйте онлайн

Достаточно прямая реализация формулы в вопросе.

Объяснение:

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 байт

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

но я верю, что это все еще можно сократить.

пример

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

Это просто молчаливая версия следующей функции:

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

С, 89

Оценка только для функции fи исключает ненужные пробелы, которые включены только для ясности. mainфункция только для тестирования.

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

Он просто сравнивает каждый символ с любым другим символом, а затем делит на общее количество сравнений.

Python 3, 56

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

Подсчитывает пары неравных элементов, затем делит на количество таких пар.

Haskell, 83 байта

Я знаю, что опоздал, нашел это, забыл опубликовать. В некотором роде нехорошо с Haskell, требующим от меня преобразовать целые числа в числа, которые вы можете разделить друг на друга.

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 байта

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

В целом, это очень незначительное улучшение по сравнению с ответом @ RetoKoradi , но в нем используется хитрый трюк:

Сумма первых n неотрицательных целых чисел равна n (n - 1) / 2 , которую мы можем использовать для вычисления числителя и знаменателя, оба разделенных на 2 , дроби в формуле вопроса.

Попробуйте онлайн в интерпретаторе CJam .

Как это устроено

 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 байт

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

Объяснение:

• ≢⍵: получить длину первого измерения ⍵. Учитывая, что ⍵предполагается, что это строка, это означает длину строки.
• {⍴⍵}⌸⍵: для каждого уникального элемента в ⍵, получить длины каждого измерения в списке вхождений. Это дает количество раз, когда элемент встречается для каждого элемента, в виде 1×≢⍵матрицы.
• ,: объединить два вдоль горизонтальной оси. Так ≢⍵как это скаляр, а другое значение является столбцом, мы получаем2×≢⍵ матрицу, в которой в первом столбце указано количество раз, которое элемент встречается для каждого элемента, а во втором столбце - общее количество элементов.
• {⍵×⍵-1}: для каждой ячейки в матрице рассчитать N(N-1).
• ÷/: уменьшить ряды делением. Это делит значение для каждого элемента на значение для общей суммы.
• +/: суммировать результат для каждой строки.
• 1-: вычтите это из 1