Wie kann man die absolute Mindestanzahl von Änderungen berechnen, um eine Sortierreihenfolge in eine andere umzuwandeln?

Question

Ziel

Wie kann man die Daten kodieren, die beschreiben, wie man eine statische Liste von einer Reihenfolge in eine andere Reihenfolge umordnet, und dabei möglichst wenige Bytes verwenden?

Ursprüngliche Motivation

Ursprünglich entstand dieses Problem bei der Arbeit an einem Problem der Weiterleitung von Sensordaten mittels teurer Satellitenkommunikation. Ein Gerät hatte eine Liste von etwa 1.000 Sensoren, die es überwachte. Die Sensorliste konnte sich nicht ändern. Jeder Sensor hatte eine eindeutige Kennung. Alle Daten wurden intern für eine spätere Analyse aufgezeichnet, und die Endbenutzer brauchten täglich nur zu wissen, welcher Sensor in welcher Reihenfolge ausgelöst hatte.

Das gesamte Projekt wurde verworfen, aber dieses Problem scheint zu interessant, um es zu ignorieren. Außerdem habe ich zuvor von "Vertauschungen" gesprochen, weil ich an den Sortieralgorithmus dachte, aber in Wirklichkeit ist die Gesamtreihenfolge wichtig, die Schritte, die erforderlich sind, um zu dieser Reihenfolge zu gelangen, spielen wahrscheinlich keine Rolle.

Wie die Daten geordnet wurden

In SQL-Begriffen könnte man es sich so vorstellen.

**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

Annahmen

• Die Anfangs- und die Endliste bestehen aus genau denselben Elementen
• Jeder Sensor hat eine eindeutige Kennung (32-Bit-Ganzzahl)
• Der Umfang der Liste wird etwa 1.000 Positionen betragen.
• Jeder Sensor kann mehrmals pro Minute oder tagelang überhaupt nicht ausgelöst werden.
• Nur die Änderung der ID-Sortierreihenfolge muss weitergegeben werden.
• Rechenressourcen für die Ermittlung optimaler Lösungen sind billig/unbegrenzt
• Die Datenkosten sind teuer, etwa ein Dollar pro Kilobyte.
• Daten konnten nur in ganzen Byte-(Oktett-)Schritten gesendet werden
• Der Auftrag von Tag 0 ist dem Sender und dem Empfänger bekannt, um mit
• Gehen Sie zunächst davon aus, dass das System einwandfrei funktioniert und keine Fehlerprüfung erforderlich ist.

Wie gesagt, das Projekt bzw. die Hardware gibt es nicht mehr, so dass dies jetzt nur noch ein akademisches Problem ist.

Die Herausforderung!

Definieren Sie einen Encoder

• Gegeben A. Tag N Sortierreihenfolge
• Gegeben B. Tag N + 1 Sortierreihenfolge
• Rückgabe C. eine Sammlung von Bytes, die beschreiben, wie A in B umgewandelt werden kann, wobei die geringstmögliche Anzahl von Bytes verwendet wird

Einen Decoder definieren

• Gegeben A. Tag N Sortierreihenfolge
• Gegeben B. eine Sammlung von Bytes
• Rückgabe C. Tag N + 1 Sortierreihenfolge

Ich wünsche allen viel Spaß.

Answer 1

Als akademisches Problem könnte man sich den Algorithmus P in Abschnitt 3.3.2 von Band II von Knuths The Art of Computer Programming ansehen, der jede Permutation von N Objekten auf eine ganze Zahl zwischen 0 und N!-1 abbildet. Wenn jede mögliche Permutation zu jedem Zeitpunkt gleich wahrscheinlich ist, dann ist das Beste, was man tun kann, die Berechnung und Übermittlung dieser (mehrfach präzisen) ganzen Zahl. In der Praxis würde es fast genauso gut funktionieren, jedem Sensor eine 10-Bit-Zahl zu geben und diese 10-Bit-Zahlen dann so zusammenzupacken, dass z. B. 4 Zahlen in jedes 5-Byte-Stück gepackt werden.

Schemata, die auf Diff oder Standardkomprimierung basieren, nutzen das Wissen, dass nicht alle Permutationen gleich wahrscheinlich sind. Vielleicht wissen Sie dies aufgrund der Ausrüstung, oder Sie können anhand früherer Daten feststellen, ob dies der Fall ist. Gut, wenn es funktioniert. In einigen Fällen mit Sensoren und Satelliten sollten Sie sich über seltene Ausnahmen Gedanken machen, bei denen Ihr Kompressionsschema im schlimmsten Fall nicht funktioniert und Sie plötzlich mehr Daten übertragen müssen, als Sie erwartet haben.