algorithm - How to compute the absolute minimum amount of changes to convert one sortorder into another? -

goal

how encode data describes how re-order static list 1 order order using minimum amount of bytes possible?

original motivation

originally problem arose while working on problem relaying sensor data using expensive satellite communication. device had list of 1,000 sensors monitoring. sensor list couldn't change. each sensor had unique id. data being logged internally eventual analysis, thing end users needed daily sensor fired in order.

the entire project scrapped, problem seems interesting ignore. talked "swaps" because thinking of sorting algorithm, it's overall order that's important, steps required arrive @ order wouldn't matter.

how data ordered

in sql terms think of this.

**initial load**  create table sensor ( id int, last_detected datetime, other stuff ) -- fill table ids of sensors location  day 0: select id sensor order id   (initially data sorted sensor.id because known value)  day 1: select id sensor order last_detected day 2: select id sensor order last_detected day 3: select id sensor order last_detected 

assumptions

• the starting list , ending list composed of exact same set of items
• each sensor has unique id (32 bit integer)
• the size of list approximately 1,000 items
• each sensors may fire multiple times per minute or not @ days
• only change in id sort order needs relayed.
• computation resources figuring optimal solutions cheap / unlimited
• data costs expensive, dollar per kilobyte.
• data sent whole byte (octet) increments
• the day 0 order known sender , receiver start with
• for assume system functions , no error checking required

as said project/hardware no more academic problem.

the challenge!

define encoder

• given a. day n sort order
• given b. day n + 1 sort order
• return c. collection of bytes describe how convert b using least number of bytes possible

define decoder

• given a. day n sort order
• given b. collection of bytes
• return c. day n + 1 sort order

have fun everyone.

as academic problem, 1 approach @ algorithm p section 3.3.2 of vol ii of knuth's art of computer programming, maps every permutation on n objects integer between 0 , n!-1. if every possible permutation equally @ time, best can compute , transmit (multi-precision) integer. in practice, giving each sensor 10-bit number , packing 10 bit numbers have e.g. 4 numbers packed each chunk of 5 bytes well.

schemes based on diff or off shelf compression make use of knowledge not permutations equally likely. may have knowledge of based on equipment, or see if case looking @ previous data. fine if works. in cases sensors , satellites might want worry rare exceptions worst case behaviour of compression scheme , have more data transmit bargained for.