Dado:
- Un número natural S .
- Una lista de N pesos ponderales W que suman 1.
Devuelve una lista L de N enteros no negativos, de modo que:
(1) sum(L) = S
(2) sum((S⋅W_i - L_i)^2) is minimal
En otras palabras, aproxima S⋅W_i
s con números enteros lo más cerca posible.
Ejemplos:
1 [0.4 0.3 0.3] = [1 0 0]
3 [0 1 0] = [0 3 0]
4 [0.3 0.4 0.3] = [1 2 1]
5 [0.3 0.4 0.3] = [2 2 1] or [1 2 2] but not [1 3 1]
21 [0.3 0.2 0.5] = [6 4 11]
5 [0.1 0.2 0.3 0.4] = [1 1 1 2] or [0 1 2 2]
4 [0.11 0.3 0.59] = [1 1 2]
10 [0.47 0.47 0.06] = [5 5 0]
10 [0.43 0.43 0.14] = [4 4 2]
11 [0.43 0.43 0.14] = [5 5 1]
Reglas:
- Puede usar cualquier formato de entrada, o simplemente proporcionar una función que acepte la entrada como argumentos.
Antecedentes:
Este problema surge cuando se muestran S de diferentes tipos de elementos en diferentes proporciones W i con respecto a los tipos.
Otro ejemplo de este problema es la representación política proporcional, ver la paradoja de la distribución . Los dos últimos casos de prueba se conocen como la paradoja de Alabama.
Como estadístico, reconocí este problema como equivalente a un problema encontrado en la identificación de tamaños de muestra al realizar una muestra estratificada. En esa situación, queremos hacer que la proporción de cada estrato en la muestra sea igual a la proporción de cada estrato en la población. - @tomi
fuente
round(A + B) != round(A) + round(B)
una solución corta requiere una idea de lo que está sucediendo aquí.L[i] - S*W[i]
cuadrado, en lugar de la regla 2 y la regla 3. Esto sería aproximadoS*W[i]
.[0 1 2 2]
es otra posible solución para5 [0.1 0.2 0.3 0.4]
Respuestas:
APL, 21
Esta es una traducción de la respuesta CJam de 37 bytes de aditsu .
Pruébelo en línea .
Explicación
fuente
Pitón 2,
9583132125143Mi primer (y segundo) (y tercer) algoritmo tuvo problemas, así que después de una (¡otra!) Reescritura y más pruebas, aquí está (realmente espero) una solución correcta y rápida:
La fuente antes del minificador ahora se ve así:
Las pruebas regresan:
Este algoritmo es similar a otras respuestas aquí. Es O (1) para num, por lo que tiene el mismo tiempo de ejecución para los enteros 10 y 1000000. Teóricamente es O (nlogn) para el número de pesos (debido al tipo). Si esto resiste todos los demás casos de entrada difíciles, reemplazará el algoritmo a continuación en mi caja de herramientas de programación.
Por favor, no use ese algoritmo con nada que no sea de golf. Hice compromisos en la velocidad para minimizar el tamaño de la fuente. El siguiente código usa la misma lógica pero es mucho más rápido y más útil:
El valor de num no afecta significativamente la velocidad. Lo he probado con valores del 1 al 10 ^ 19. El tiempo de ejecución varía linealmente con el número de pesos. En mi computadora, tarda 0,15 segundos con 10 ^ 5 pesos y 15 segundos con 10 ^ 7 pesos. Tenga en cuenta que los pesos no están restringidos a fracciones que suman uno. La técnica de clasificación utilizada aquí también es aproximadamente dos veces más rápida que el
sorted((v,i) for i,v in enumerate...)
estilo tradicional .Algoritmo Original
Esta fue una función en mi caja de herramientas, modificada un poco para el golf. Originalmente fue de una respuesta SO . Y está mal.
Da una aproximación, pero no siempre es correcta, aunque se mantiene la suma (outseq) == num. Rápido pero no recomendado.
Gracias a @alephalpha y @ user23013 por detectar los errores.
EDITAR: Establezca totalw (d) en 1, ya que OP especifica que la suma de los pesos siempre será 1. Ahora 83 bytes.
EDIT2: Se corrigió el error encontrado para [0.4, 0.3, 0.3], 1.
EDIT3: Algoritmo defectuoso abandonado. Se agregó uno mejor.
EDIT4: Esto se está volviendo ridículo. Reemplazado con el algoritmo correcto (realmente espero).
EDITAR5: Se agregó código que no es de golf para otros que quieran usar este algoritmo.
fuente
a([0.4, 0.3, 0.3], 1)
vuelve[0, 1, 0]
, mientras que la respuesta correcta es[1, 0, 0]
.a([0.11,0.3,0.59],4)
devuelto[0, 1, 3]
. Debe ser[1, 1, 2]
.f([0.47,0.47,0.06],10)
devuelto[5, 4, 1]
. Debe ser[5, 5, 0]
.Mathematica,
67504645 caracteresSin golf:
Ejemplo:
fuente
CJam - 37
Pruébalo en línea
Explicación:
Notas:
Idea diferente - 46
Pruébalo en línea
Esto es mucho más sencillo y eficiente, pero, por desgracia, es un poco más largo. La idea aquí es comenzar con L_i = floor (S * W_i), determinar la diferencia (digamos D) entre S y su suma, encontrar los índices D con la mayor parte fraccional de S * W_i (ordenando y tomando D superior) e incremente L_i para esos índices. Complejidad O (N * log (N)).
fuente
:e<
.JavaScript (ES6) 126
130 104 115 156 162 194Después de todos los comentarios y casos de prueba en la respuesta de @ CarpetPython, volviendo a mi primer algoritmo. Por desgracia, la solución inteligente no funciona. La implementación se acortó un poco, aún intenta todas las soluciones posibles, calcula la distancia al cuadrado y mantiene el mínimo.
Editar Para cada elemento de salida de peso w, 'todos' los valores posibles son solo 2: trunc (w * s) y trunc (w * s) +1, por lo que solo hay (2 ** elementos) posibles soluciones para probar.
Prueba en la consola Firefox / FireBug
Salida
Esa es una solución más inteligente. Paso único en matriz de pesos.Para cada pase, encuentro el valor máximo actual en w. Cambio este valor en su lugar con el valor entero ponderado (redondeado hacia arriba), por lo que si s == 21 yw = 0.4, obtenemos 0.5 * 21 -> 10.5 -> 11. Almaceno este valor negado, por lo que no puede se encuentra como máximo en el siguiente ciclo. Luego reduzco la suma total en consecuencia (s = s-11) y también reduzco el total de los pesos en la variable f.
El ciclo finaliza cuando no se encuentra un máximo por encima de 0 (todos los valores! = 0 se han gestionado).
Por fin devuelvo los valores cambiados a positivo nuevamente. Advertencia: este código modifica la matriz de pesos en su lugar, por lo que debe llamarse con una copia de la matriz original
Mi primer intento
No es una solución tan inteligente. Para cada resultado posible, evalúa la diferencia y mantiene el mínimo.
Desengañado y explicado
fuente
CJam, 48 bytes
Una solución directa al problema.
La entrada va como
Explicación:
Pruébalo en línea aquí
fuente
Pyth: 40 bytes
Esto define una función
g
con 2 parámetros. Puedes llamarlo asíMhosm^-*Ghded2C,HNfqsTGmms+*G@Hb}bklHyUHg5 [0.1 0.2 0.3 0.4
.Pruébelo en línea: Pyth Compiler / Executor
Explicación:
Esto crea todas las soluciones posibles
L
, dondeL[i] = floor(S*W[i])
oL[i] = floor(S*W[i]+1)
. Por ejemplo, la entrada4 [0.3 0.4 0.3
crea[[1, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 2], [2, 2, 1], [2, 1, 2], [1, 2, 2], [2, 2, 2]]
.Solo
[[2, 1, 1], [1, 2, 1], [1, 1, 2]]
queda.fuente
Mathematica 108
Explicación
Sin golf
IntegerPartitions[s,{Length@w},0~Range~s]
devuelve todos los tabiques enteros des
, utilizando elementos tomados del conjunto{0, 1, 2, ...s}
con la restricción de que la salida debe contener el mismo número de elementos que en el conjunto de pesos,w
.Permutations
da todos los arreglos ordenados de cada partición entera.{Tr[(s *w-#)^2],#}
devuelve una lista de pares ordenados,{error, permutation}
para cada permutación.Sort[...]
ordena la lista de{{error1, permutation1},{error2, permutation2}...according to the size of the error.
[[1,2]]]
oPart[<list>,{1,2}]
devuelve el segundo elemento del primer elemento en la lista ordenada de{{error, permutation}...}
. En otras palabras, devuelve la permutación con el error más pequeño.fuente
R,
858076Utiliza el método de cuota de liebre.
Se eliminó un par después de ver la especificación de que W sumará a 1
Prueba de funcionamiento
fuente
Python,
139128117 bytesSolución itertools anterior, 139 bytes
fuente
O(S^len(W))
realidad: P. La nueva solución es mucho más rápida, pero aún lentaOctava,
8776Golfizado:
Sin golf:
(¡Maldito "endfor" y "endfunction"! Nunca ganaré pero disfruto jugando al golf con un lenguaje "real").
fuente
zeros(size(w))
con0*w
.T-SQL,
167265Porque me gusta probar y hacer estos desafíos también en una consulta.
Lo convirtió en una función en línea para ajustarse mejor a la especificación y creó un tipo para los datos de la tabla. Costó un poco, pero esto nunca iba a ser un contendiente. Cada declaración debe ejecutarse por separado.
En uso
fuente