Índice de diversidad de Simpson

19

El índice de Simpson es una medida de la diversidad de una colección de elementos con duplicados. Es simplemente la probabilidad de sacar dos elementos diferentes al elegir sin reemplazo de manera uniforme al azar.

Con nelementos en grupos de n_1, ..., n_kelementos idénticos, la probabilidad de dos elementos diferentes es

$$ 1- \ sum_ {i = 1} ^ k \ frac {n_i (n_i-1)} {n (n -1)} $$

Por ejemplo, si tiene 3 manzanas, 2 plátanos y 1 zanahoria, el índice de diversidad es

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

Alternativamente, el número de pares desordenados de artículos diferentes es 3*2 + 3*1 + 2*1 = 11de 15 pares en general, y 11/15 = 0.7333.

Entrada:

Una cadena de caracteres Apara Z. O una lista de tales personajes. Su longitud será de al menos 2. No puede suponer que está ordenada.

Salida:

El índice de diversidad de Simpson de caracteres en esa cadena, es decir, la probabilidad de que dos caracteres tomados al azar con reemplazo sean diferentes. Este es un número entre 0 y 1 inclusive.

Al emitir un flotante, muestre al menos 4 dígitos, aunque finalice salidas exactas como 1o 1.0o 0.375están bien.

No puede utilizar elementos integrados que computen específicamente índices de diversidad o medidas de entropía. El muestreo aleatorio real está bien, siempre que obtenga suficiente precisión en los casos de prueba.

Casos de prueba

AAABBC 0.73333
ACBABA 0.73333
WWW 0.0
CODE 1.0
PROGRAMMING 0.94545

Tabla de clasificación

Aquí hay una tabla de clasificación por idioma, cortesía de Martin Büttner .

Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntuación, se puede mantener viejas cuentas en el título, golpeándolos a través. Por ejemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

xnor
fuente
Estás usando el índice de Gini-Simpson, cuando una medida mucho mejor para usar es el índice inverso de Simpson, también conocido como número efectivo de tipos.
Joe Z.
1
Básicamente en 1/lugar de 1-. [estadístico aficionado despotricar]
Joe Z.

Respuestas:

5

Pitón 2, 72

La entrada puede ser una cadena o una lista.

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

Ya sé que sería 2 bytes más corto en Python 3, así que no me lo aconsejen :)

Feersum
fuente
¿Qué están <>haciendo los corchetes angulares en la posición 36? Nunca he visto esa sintaxis antes.
ApproachingDarknessFish
@TuttiFruttiJacuzzi: es sinónimo de !=.
RemcoGerlich
1
@TuttiFruttiJacuzzi Solo es Python 2 a menos que ustedfrom __future__ import barry_as_FLUFL
matsjoyce
@ Vioz- No con el l=len(s);de allí
Sp3000
@ Sp3000 Correcto, no noté cuántas veces se utilizó.
Kade
4

Pyth - 19 13 12 11 bytes

Gracias a @isaacg por contarme sobre n

Utiliza el enfoque de fuerza bruta con la .cfunción de combinaciones.

csnMK.cz2lK

Pruébalo aquí en línea .

Banco de pruebas .

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
Maltysen
fuente
Puede reemplazar .{con n- son equivalentes aquí.
isaacg
@isaacg, oh, no sabía que salpican automáticamente, genial.
Maltysen
4

SQL (PostgreSQL), 182 bytes

Como una función en 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

Explicación

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 y prueba de funcionamiento

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
MickyT
fuente
4

J 26 bytes

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

la parte genial

Encontré los recuentos de cada personaje tecleando </.la cadena contra sí mismo ( ~para reflexivo) y luego contando las letras de cada cuadro.

protista
fuente
1
(#&:>@</.~)puede ser (#/.~)y (<:*])puede ser (*<:). Si utiliza una función adecuada, esto le da (1-(#/.~)+/@:%&(*<:)#). Como las llaves circundantes generalmente no se cuentan aquí (dejando 1-(#/.~)+/@:%&(*<:)#, el cuerpo de la función) esto da 20 bytes.
randomra
4

Python 3, 66 58 Bytes

Esto está utilizando la fórmula de conteo simple proporcionada en la pregunta, nada demasiado complicado. Es una función lambda anónima, por lo que para usarla, debe darle un nombre.

Guardado 8 bytes (!) Gracias a 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

o

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

APL, 39 36 bytes

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

Esto crea una mónada sin nombre.

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

¡Puedes probarlo en línea !

Alex A.
fuente
2

Pyth, 13 bytes

csnM*zz*lztlz

Prácticamente una traducción literal de la solución de @ feersum.

orlp
fuente
2

CJam, 25 bytes

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

Pruébalo en línea

Implementación bastante directa de la fórmula en la pregunta.

Explicación:

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.
Reto Koradi
fuente
1

J, 37 bytes

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

pero creo que aún se puede acortar.

Ejemplo

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

Esta es solo una versión tácita de la siguiente función:

   fun =: 3 : 0
a1=.+/"1 (~.y)=/y
N=.(+/a1)*(<:+/a1)
n=.a1*a1-1
1-(+/n)%N
)
gar
fuente
Después de jugar al golf extra y hacer que sea una función adecuada: (1-(%&([:+/]*<:)+/)@(+/"1@=))da 29 bytes. 27 si no contamos las llaves que rodean la función, (1-(%&([:+/]*<:)+/)@(+/"1@=))ya que es común aquí. Notas: =yes exactamente (~.=/])yy la conjunción de composición ( x u&v y= (v x) u (v y)) también fue muy útil.
randomra
Gracias por las sugerencias! Todavía estoy aprendiendo a escribir expresiones tácitas yo mismo. Por ahora, uso 13: 0 para generar definiciones tácitas parte por parte y combinarlas.
gar
1

C, 89

La puntuación es solo para la función fy excluye espacios en blanco innecesarios, que solo se incluyen para mayor claridad. La mainfunción es solo para pruebas.

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

Simplemente compara cada personaje con cualquier otro personaje, luego lo divide por el número total de comparaciones.

Level River St
fuente
1

Pitón 3, 56

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

Cuenta los pares de elementos desiguales, luego divide por el número de tales pares.

xnor
fuente
1

Haskell, 83 bytes

Sé que llego tarde, encontré esto, había olvidado publicar. Un poco poco elegante con Haskell requiriéndome convertir números enteros en números que se pueden dividir entre sí.

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

CJam, 23 bytes

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

En cuanto al byte, esta es una mejora muy pequeña sobre la respuesta de @ RetoKoradi , pero utiliza un buen truco:

La suma de los primeros n enteros no negativos es igual a n (n - 1) / 2 , que podemos usar para calcular el numerador y el denominador, ambos divididos por 2 , de la fracción en la fórmula de la pregunta.

Pruébelo en línea en el intérprete de CJam .

Cómo 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.
Dennis
fuente
0

APL, 26 bytes

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

Explicación:

  • ≢⍵: obtiene la longitud de la primera dimensión de . Dado que se supone que es una cadena, esto significa la longitud de la cadena.
  • {⍴⍵}⌸⍵: para cada elemento único en , obtenga las longitudes de cada dimensión de la lista de ocurrencias. Esto proporciona la cantidad de veces que ocurre un elemento para cada elemento, como una 1×≢⍵matriz.
  • ,: concatenar los dos a lo largo del eje horizontal. Como ≢⍵es un escalar, y el otro valor es una columna, obtenemos una 2×≢⍵matriz donde la primera columna tiene la cantidad de veces que ocurre un elemento para cada elemento, y la segunda columna tiene la cantidad total de elementos.
  • {⍵×⍵-1}: para cada celda en la matriz, calcular N(N-1).
  • ÷/: reduce filas por división. Esto divide el valor de cada artículo por el valor del total.
  • +/: suma el resultado para cada fila.
  • 1-: restarlo de 1
marinus
fuente