¿Cómo calcular la cantidad mínima absoluta de cambios para convertir un sortorder en otro?

Question

Meta

Cómo codificar los datos que describe cómo volver a ordenar una lista estática de un un orden a otro orden utilizando la mínima cantidad de bytes posibles?

motivación original

Originalmente, este problema se presentó mientras se trabaja en un problema de transmisión de datos de sensores que utilizan la comunicación por satélite caro. Un dispositivo tenía una lista de aproximadamente 1,000 sensores que estaban monitoreando. La lista de sensores no pudo cambiar. Cada sensor tenía una identificación única. Todos los datos se registraron internamente para el análisis final, lo único que los usuarios finales necesitaban diariamente era qué sensor disparaba en qué orden.

Se eliminó todo el proyecto, pero este problema parece demasiado interesante como para ignorarlo. También anteriormente hablé de "swaps" porque estaba pensando en el algoritmo de clasificación, pero en realidad es el orden general lo que es importante, los pasos necesarios para llegar a esa orden probablemente no importarían.

que haya pedido los datos

En términos de SQL que se podría pensar en ello como esto.

**Initial Load** 

create table sensor (id int, last_detected datetime, other stuff) 
-- fill table with ids of all sensors for this location 

Day 0: Select ID from Sensor order by id 
    (initially data is sorted by the sensor.id because its a known value) 

Day 1: Select ID from Sensor order by last_detected 
Day 2: Select ID from Sensor order by last_detected 
Day 3: Select ID from Sensor order by last_detected 

Supuestos

• La lista de partida y de la lista que termina se compone de exactamente el mismo conjunto de elementos
• Cada sensor tiene un identificador único (número entero de 32 bits)
• El tamaño de la lista será de aproximadamente 1,000 artículos
• Cada sensor puede disparar varias veces por minuto o no hacerlo en los días
• Solo es necesario retransmitir el cambio en el orden de clasificación de ID.
• Los recursos de cálculo para calcular soluciones óptimas son baratos/ilimitados
• Los costos de los datos son aproximadamente de un dólar por kilobyte.
• datos sólo pueden ser enviados como byte conjunto (octeto) incrementos
• El orden del día 0 es conocida por el emisor y el receptor para comenzar con
• Por ahora asumir las funciones del sistema a la perfección y no se requiere la comprobación de errores

Como he dicho, el proyecto/hardware ya no existe, así que esto es solo un problema académico.

¡El desafío!

Definir un codificador

• Dada A. Día N orden de clasificación
• Dada B. Día N + 1 orden de clasificación
• Return C.una colección de bytes que describen cómo convertir la A a la B, utilizando el menor número de bytes posibles

definir un decodificador

• Dada A. Día N orden de clasificación
• Dada una colección de B. bytes
• Retorno C. Día N + 1 orden de clasificación

Diviértete todo el mundo.

Answer 1

Como problema académico, un enfoque sería observar el Algoritmo P, sección 3.3.2 del Vol II del arte de la programación de Knuth, que mapea cada permutación en N objetos en un número entero entre 0 y N! -1 . Si cada permutación posible es igualmente probable en cualquier momento, lo mejor que puede hacer es calcular y transmitir este entero (multi-precisión). En la práctica, dando a cada sensor un número de 10 bits y luego empacando esos 10 bits para que tenga, por ejemplo, 4 números empaquetados en cada porción de 5 bytes lo harían casi tan bien.

Los esquemas basados ​​en compresión diff o fuera de la plataforma hacen uso del conocimiento de que no todas las permutaciones son igualmente probables. Puede tener conocimiento de esto basado en el equipo, o puede ver si es este caso al mirar datos anteriores. Bien si funciona En algunos casos, con sensores y satélites, es posible que desee preocuparse por raras excepciones donde obtiene el peor comportamiento de caso de su esquema de compresión y de repente tiene más datos para transmitir de los que esperaba.