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

Question

Tor

Wie die Daten kodieren, die wie möglich eine statische Liste von einem einem Auftrag an einem anderen Auftrag mit der minimalen Menge von Bytes neu zu ordnen beschreiben?

Ursprüngliche Motivation

Ursprünglich dieses Problem entstand, während auf einem Problem Arbeitssensordatenvermittlungs mit teuerer Satellitenkommunikation. Ein Gerät hatte eine Liste von etwa 1.000 Sensoren, die überwacht wurden. Die Sensorliste konnte nicht geändert werden. Jeder Sensor hatte eine eindeutige ID. Alle Daten wurden intern für eine spätere Analyse protokolliert. Das einzige, was Endbenutzer täglich benötigten, war, welcher Sensor in welcher Reihenfolge ausgelöst wurde.

Das gesamte Projekt wurde verschrottet, aber dieses Problem scheint zu interessant zu sein, um es zu ignorieren. Auch vorher habe ich von "Swaps" gesprochen, weil ich an den Sortieralgorithmus gedacht habe, aber eigentlich ist es die gesamte Reihenfolge, die wichtig ist, die Schritte, die erforderlich sind, um zu dieser Reihenfolge zu gelangen, wären wahrscheinlich egal.

Wie die Daten bestellt wurde

In SQL Bedingungen könnten Sie es wie folgt denken.

**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 Startliste und endend Liste wird
der exakt gleichen Menge von Elementen zusammengesetzt
• Jeder Sensor hat eine eindeutige ID (32 Bit-Ganzzahl)
• Die Größe der Liste wird etwa 1.000 Artikel sein
• Jeder Sensor kann mehrere Male pro Minute oder gar nicht für Tage
auslösen
• Nur die Änderung der ID-Sortierreihenfolge muss weitergeleitet werden.
• Rechenressourcen für die Berechnung der optimalen Lösungen ist billig/unbegrenzt
• Datenkosten sind teuer, etwa ein Dollar pro Kilobyte.
• Daten nur als ganzes Byte (Oktett) gesendet erhöht mit
• Vorerst bekannt ist, zu beginnen übernimmt die Systemfunktionen perfekt und keine Fehlerprüfung erforderlich ist
• Die Tag 0 Bestellung durch den Sender und Empfänger werden könnten

Wie ich schon sagte das Projekt/Hardware ist nicht mehr so ​​ist dies jetzt nur ein akademisches Problem.

Die Herausforderung!

einen Encoder definieren

• A. Day N Sortierung
• bestellen
• Return C. Bei B. Day N + 1 Art Gegebenunter Verwendung der geringsten Anzahl von Bytes möglich

definieren einen Decoder

eine Ansammlung von Bytes, die beschreiben, wie A nach B zu konvertieren
• A. Day N Sortierung
• B. eine Sammlung von Gegeben Gegeben Bytes
• Return C. Day N + 1 Sortierreihenfolge

Viel Spaß jedermann.

Answer 1

Als ein akademisches Problem wäre ein Ansatz, Algorithmus P Abschnitt 3.3.2 von Band II von Knuth's Kunst der Computerprogrammierung zu betrachten, der jede Permutation auf N Objekten in eine ganze Zahl zwischen 0 und N! -1 abbildet . Wenn jede mögliche Permutation zu jeder Zeit gleich wahrscheinlich ist, dann ist das Beste, was Sie tun können, diese (Vielpräzisions-) Ganzzahl zu berechnen und zu übertragen. In der Praxis geben Sie jedem Sensor eine 10-Bit-Zahl und verpacken diese 10-Bit-Zahlen dann, so dass Sie z.B. 4 Zahlen, die in jeden Block von 5 Bytes gepackt wurden, würden fast genauso gut funktionieren.

Schemata, die auf Diff- oder Off-Shelf-Komprimierung basieren, nutzen das Wissen, dass nicht alle Permutationen gleich wahrscheinlich sind. Je nachdem, welches Gerät Sie verwenden, können Sie davon Kenntnis haben, oder Sie können anhand der vorherigen Daten sehen, ob dies der Fall ist. Gut, wenn es funktioniert. In einigen Fällen mit Sensoren und Satelliten können Sie sich über seltene Ausnahmen Gedanken machen, bei denen Sie im schlimmsten Fall ein Verhalten Ihres Komprimierungsschemas bekommen und plötzlich mehr Daten übertragen werden, als Sie erwartet haben.