Estoy buscando un algoritmo para distribuir valores de una lista para que la lista resultante esté lo más "equilibrada" o "distribuida de manera uniforme" posible (entre comillas porque no estoy seguro de que estas sean las mejores formas de describirla ... más adelante proporcionaré una forma de medir si un resultado es mejor que otro).
Entonces, para la lista:
[1, 1, 2, 2, 3, 3]
Uno de los mejores resultados, después de redistribuir los valores, es:
[1, 2, 3, 1, 2, 3]
Puede haber otros resultados tan buenos como este y, por supuesto, esto se vuelve más complicado con un conjunto de valores menos uniforme.
Así es como medir si un resultado es mejor que otro:
Cuente las distancias entre cada elemento y el siguiente elemento con el mismo valor.
Calcule la desviación estándar para ese conjunto de distancias. Una dispersión más baja significa un mejor resultado.
Observaciones:
- Cuando se calcula una distancia y se alcanza el final de la lista sin encontrar un elemento con el mismo valor, volvemos al principio de la lista. Entonces, a lo sumo, se encontrará el mismo artículo y la distancia para ese artículo será la longitud de la lista. Esto significa que la lista es cíclica ;
- Una lista típica tiene ~ 50 artículos con ~ 15 valores diferentes en cantidades variadas.
Asi que:
- Para el resultado
[1, 2, 3, 1, 2, 3]
, las distancias son[3, 3, 3, 3, 3, 3]
y la desviación estándar es0
; - Para el resultado
[1, 1, 2, 2, 3, 3]
, las distancias son[1, 5, 1, 5, 1, 5]
y la desviación estándar es2
; - Lo que hace que el primer resultado sea mejor que el segundo (una desviación menor es mejor).
Dadas estas definiciones, pido una pista de qué algoritmos o estrategias debo buscar.
Respuestas:
Me encontré con esta pregunta mientras investigaba un problema similar: adiciones óptimas de líquidos para reducir la estratificación. Parece que mi solución también sería aplicable a su situación.
Si desea mezclar líquidos A, B y C en la proporción de 30,20,10 (es decir, 30 unidades de A, 20 unidades de B y 10 unidades de C), terminará con la estratificación si agrega todos la A, luego toda la B y luego toda la C. Es mejor mezclar unidades más pequeñas. Por ejemplo, haga adiciones de una sola unidad en la secuencia [A, B, A, C, B, A]. Eso evitará la estratificación por completo.
La forma en que lo hice es tratarlo como una especie de fusión, utilizando una cola de prioridad. Si creo una estructura para describir las adiciones:
La frecuencia se expresa como "uno cada N". Entonces, A, que se agrega tres de seis veces, tiene una frecuencia de 2 (6/3).
E inicialice un montón que inicialmente contiene:
Ahora, elimino el primer elemento del montón y lo envío. Luego reduzca su recuento en 1 y aumente la Prioridad por Frecuencia y agréguelo nuevamente al montón. El montón resultante es:
A continuación, elimine B del montón, la salida y actualícela, luego agregue nuevamente al montón:
Si continúo de esa manera, obtengo la mezcla deseada. Utilizo un comparador personalizado para garantizar que cuando se insertan elementos de prioridad iguales en el montón, se ordena primero el que tiene el valor de frecuencia más alto (es decir, el menos frecuente).
Escribí una descripción más completa del problema y su solución en mi blog, y presenté un código C # que lo ilustra. Consulte Distribución uniforme de elementos en una lista .
Actualización después de comentarios
Creo que mi problema es similar al del OP y, por lo tanto, mi solución es potencialmente útil. Pido disculpas por no enmarcar mi respuesta más en los términos de la pregunta del OP.
La primera objeción, que mi solución está usando A, B y C en lugar de 0, 1 y 2, se soluciona fácilmente. Es simplemente una cuestión de nomenclatura. Me resulta más fácil y menos confuso pensar y decir "dos A" en lugar de "dos 1". Pero para los propósitos de esta discusión, he modificado mis resultados a continuación para usar la nomenclatura del OP.
Por supuesto, mi problema trata con el concepto de distancia. Si desea "distribuir las cosas de manera uniforme", la distancia está implícita. Pero, nuevamente, fue mi fracaso por no mostrar adecuadamente cómo mi problema es similar al problema del OP.
Ejecuté algunas pruebas con los dos ejemplos que proporcionó el OP. Es decir:
En mi nomenclatura, esos se expresan como [2,2,2] y [4,3,2,1], respectivamente. Es decir, en el último ejemplo, "4 elementos del tipo 0, 3 elementos del tipo 1, 2 elementos del tipo 2 y 1 elemento del tipo 3".
Ejecuté mi programa de prueba (como se describe a continuación) y publiqué mis resultados. En ausencia del aporte del OP, no puedo decir si mis resultados son similares, peores o mejores que los suyos. Tampoco puedo comparar mis resultados con los resultados de nadie más porque nadie más ha publicado ninguno.
Sin embargo, puedo decir que el algoritmo proporciona una buena solución a mi problema de eliminar la estratificación al mezclar líquidos. Y parece que proporciona una solución razonable al problema del OP.
Para los resultados que se muestran a continuación, utilicé el algoritmo que detallé en mi entrada de blog, con la prioridad inicial establecida en
Frequency/2
, y el comparador de montón modificado para favorecer el elemento más frecuente. El código modificado se muestra aquí, con las líneas modificadas comentadas.Al ejecutar mi programa de prueba con el primer ejemplo del OP, obtengo:
Entonces mi algoritmo funciona para el problema trivial de que todos los recuentos sean iguales.
Para el segundo problema que publicó el OP, obtuve:
No veo una forma obvia de mejorar eso. Podría reorganizarse para hacer las distancias para el ítem 0 [2,3,2,3] o algún otro arreglo de 2 y 3, pero eso cambiará las desviaciones para los ítems 1 y / o 2. Realmente no sé qué "óptimo" está en esta situación. ¿Es mejor tener una desviación mayor en los artículos más frecuentes o menos frecuentes?
Al carecer de otros problemas del OP, utilicé sus descripciones para inventar algunas propias. Él dijo en su publicación:
Entonces mis dos pruebas fueron:
Y mis resultados:
Y para el segundo ejemplo:
fuente
Esto "huele" como si pudiera ser NP-duro. Entonces, ¿qué haces cuando tienes un problema NP-difícil? Lánzale una heurística o un algoritmo de aproximación, o usa un solucionador SAT.
En su caso, si no necesita la solución óptima absoluta, un punto de partida razonable podría ser intentar el recocido simulado . Hay una forma natural de tomar cualquier solución candidata y moverla a una solución candidata cercana: seleccione aleatoriamente dos elementos de la lista y cámbielos. El recocido simulado intentará iterativamente mejorar la solución. Puede encontrar muchos recursos en recocido simulado, si no está familiarizado con él. También puede experimentar con otros conjuntos de "movimientos locales" que realizan pequeños cambios en una solución candidata, con la esperanza de mejorarla gradualmente (es decir, reducir la desviación estándar de las distancias).
Pero te sugiero que comiences con recocido simulado. Eso es lo primero que intentaría, porque creo que podría funcionar.
fuente
Bosquejo de un algoritmo heurístico
No tengo una solución exacta para este problema. Pero como el comentario de Raphael sugiere que se parece al problema de la partición, para el cual se han desarrollado algoritmos heurísticos, intentaré un enfoque heurístico. Esto es solo un boceto de un algoritmo heurístico.
Eso guiará nuestro algoritmo.
Puede ser un valor con muchas o muy pocas ocurrencias al principio. Creo que en realidad no hace la diferencia, ya que las restricciones creadas por ocupar ranuras están en proporción al número de valores bien (?) Colocados.
El primer valor considerado se puede colocar sin ninguna restricción. Luego, los otros valores deben colocarse para minimizar su contribución a la desviación estándar, pero solo en los espacios que quedan libres por los valores que se hayan colocado antes.
La colocación de las ocurrencias de un valor en los espacios restantes se puede hacer con un algoritmo de programación dinámico, para fusionar los cálculos que colocan el mismo número de valores entre dos posiciones, manteniendo solo aquellos que tienen una contribución mínima a la desviación estándar (es decir, valor mínimo para la suma del cuadrado de sus desviaciones).
Luego coloca los valores singleton en las ranuras restantes.
Creo que esto generalmente debería dar una solución razonable, pero aún no tengo idea de cómo probarlo o estimar la brecha con una solución óptima.
fuente
[0, 0, 0, 0, 1, 1, 1, 2, 2, 3]
yv4
, colocaríamos primero los valores1
(10/3 = 3.33
, más cercano a v), luego2
(10/2 = 5
, siguiente más cercano), luego0
(10/4 = 2.5
)? O: ¿podría dar un ejemplo de "disminución de la desviación media de la distancia del valor v"?Parece que llego muy tarde a la fiesta, pero publicando en caso de que alguien se encuentre con esto nuevamente. Mi solución es similar a @ babou's plus. Hoy temprano, tuve un problema de programación en un sistema embebido que me llevó a este hilo. Tengo una implementación específica para mi problema en C, pero pensé que publicaría una solución más genérica en Python aquí (la versión C es complicada por el hecho de que me he restringido a una pila pequeña de tamaño fijo y sin memoria asignaciones, por lo que realizo todo el algoritmo en el lugar). La técnica de suavizado utilizada a continuación es algo que puede usar para dibujar una línea en una pantalla con color de 2 bits. El algoritmo aquí logra una puntuación más baja (es decir, mejor) cuando se mide usando la suma de la desviación estándar para las entradas utilizadas por Jim Mischel que esa solución en particular.
resultados para
Si se proporcionan entradas de la forma especificada por @moraes, se puede convertir a una forma utilizable por esta función en pasos O (n) utilizando Big Omega (n * log (n)) bits de memoria donde n es el número de elementos ( en una lista con 255 elementos, no necesitará más de 255 bytes adicionales) manteniendo una matriz paralela con los recuentos de repetición. Alternativamente, uno puede realizar un par de clases en el lugar con O (1) memoria adicional.
PD
Editar: Sé que esta solución no produce la salida óptima por contraejemplo. Una entrada de
[6, 2, 1]
produce[0, 1, 0, 0, 2, 0, 0, 1, 0]
; Una mejor solución es[0, 0, 1, 0, 2, 0, 0, 1, 0]
.fuente
Este algoritmo funciona con una matriz de enteros, donde cada entero representa una categoría diferente. Crea matrices separadas para cada categoría. Por ejemplo, si la matriz inicial es [1, 1, 1, 2, 2, 3], creará tres matrices, [3], [2, 2], [1, 1, 1].
A partir de ahí, combina recursivamente las dos matrices más pequeñas (en este ejemplo, [3] y [2,2]) y espacia la ubicación de los elementos de la matriz más pequeña en la segunda matriz más pequeña, basándose principalmente en la relación del número de ocurrencias de las categorías más grandes frente a las más pequeñas. En este ejemplo, terminaríamos con [2,3,2]. Luego usaría esta matriz como la matriz más pequeña que se combinará en la siguiente matriz más grande, hasta que solo quede una matriz.
fuente
CÓDIGO ANSI C
Este código funciona imaginando una línea recta en n espacio dimensional (donde n es el número de categorías) que pasa por el origen con el vector direccional (v1, v2, ..., vi, ... vn) donde vi es el número de artículos en la categoría i. Comenzando desde el origen, el objetivo es encontrar el siguiente punto más cercano a la línea. Usando el ejemplo [0 0 0 0 0 1 1 1 2 2 2 3] produce el resultado [0 1 2 0 3 1 0 2 0 1 2 0]. Usando el ejemplo de Lungj [0 0 0 0 0 0 1 1 2] obtenemos [0 1 0 0 2 0 0 1 0], que es exactamente el mismo que el resultado de Lungj.
El algoritmo se hace más eficiente usando solo aritmética de enteros y considerando solo los deltas entre las distancias desde cada punto a la línea.
#define MAXCATEGORIES 100
int main () {int i = 0; int j = 0; int catsize = 0; int vector [MAXCATEGORIES]; punto int [MAXCATEGORIES]; int categorías = 0; int totalitems = 0; int mejor = 0; largo d2 = 0L; largo vp = 0L; largo v2 = 0L; delta largo = 0L; beta largo = 0L;
}
fuente
mi solución:
fuente