Problem: re-order correction code

gistfile1.txt

Problem: re-order correction code

You need to send a message through a datagram channel which may reorder
packets.  It only reorder packets, but not drop or duplicate packets.  You are
asked to design an efficient error correction code that can reliably deliver a
message.  Minimal packets should be used.  Specifically, you need to design two
functions (Java syntax for illustration purpose):

1. byte[][] encode (byte[] message, int packetSize)
2. byte[] decode (byte[][] packets)

Assumptions:
1. 1 <= packetSize <= 4
2. 0 <= message.length <= 1,000,000 (The only concern here is memory)

Requirements:
1. The size of all packets returned by send() must be packetSize.
2. After B=send(A,n); C=shuffle(B); D=receive(C); , D must be same as A.
3. The number of packets returned by send() should be minimal.

A naive approach:

We can use the first byte to record the order information.  Assume packet size
= 2, message = HELLOWORLD.  We can encode it into 10 packets: aH, bE, cL, dL,
eO, fW, gO, hR, iL and jD.  The decoder will first sort the 10 packets using
the first byte and then extract the second byte as the message.  This approach
is obviously not optimal.

A related problem:

You can send 4 packets, each 6 bytes. Packet reordering can happen as stated
above. How many bits of information can you send and how to send? In theory,
4*6*8 - log2(4!) = 187.41 bits of information are contained in the 4 packets.
Can you design a code to encode 187 bits?