Usbrth

The problem is purely mathematic because they are the dominant combinatorics and probability. It is possible to solve the problem without knowing programming, but it is much easier to solve it by programming.

In the following 40 byte group, there are 3 pairs of the same bytes:

248, 195, 38, 169, 202, 202, 133, 240, 232, 204, 142, 40, 86, 89, 215, 138, 15, 217, 123, 33, 183, 105, 239, 239, 229, 192, 226, 191, 23, 158, 12, 94, 222, 253, 6, 113, 146, 146, 183, 209.

A pair of bytes 169 202 is a pair of different bytes. A pair of bytes 202 202 is a pair of the same bytes.

Bytes must be shuffled so that the pairs of the same bytes do not appear. The resulting bytes must be composed only of pairs of different bytes!

Example of resultant bytes (swap 2*n and 2*n+1 byte, n=1..19) :

248, 38, 195, 202, 169, 133, 202, 232, 240, 142, 204, 86, 40, 215, 89, 15, 138, 123, 217, 183, 33, 239, 105, 229, 239, 226, 192, 23, 191, 12, 158, 222, 94, 6, 253, 146, 113, 183, 146, 209.

The procedure must be reversible. Instead of 40 bytes (in case of example), the procedure should be applied to a group of 1500 bytes. In a group of 1500 bytes, most pairs are different bytes. There are also pairs with the same bytes, but there are no more than 10 and they do not know where they are in the group. Multiple consecutive same bytes do not exist. In a group of 1500 bytes, all bytes appeared at least once. If the algorithm has to use additional numbers to shuffle a group of 1500 bytes, then these numbers must be the same for each group. The algorithm does not have to be successful in every call. It is enough that from 8 consecutive different groups of 1500 bytes it succeeds to shuffle any two.

Any group of bytes from any file type can be converted into a group as described in the problem. A group of such 1500 bytes is of interest for compression and encryption.

The problem is that there is recombination of bytes - the same pairs are eliminated at the places where they were, but appear elsewhere. This problem occurs with larger groups of bytes. A 40-byte group will solve almost every well-known algorithm for shuffling numbers, but a group of 1500 bytes has not solved any one!

It is desirable to provide a solution in delphi 7 code or pseudocode.

The following procedure sufficiently well model a group of 1500 bytes:

var
 b : array [1..1500] of byte;

procedure MakePseudorandomNumbersWithEqualPairs (sum : longint; max : word);
var
 i, lastb : longint;
 range : word;
begin
 Randomize; // Prepare a random number generator
 lastb := sum; // How many total bytes
 range := max; // Bytes from the range 0..max-1
 for i := 1 to lastb do // They can be the same neighbors! 
 b[i] := Random (range);
end;

After the procedure call:

MakePseudorandomNumbersWithEqualPairs (1500, 256);

array b contains bytes that model the given group.

What I have tried:

const
 lastb = 1500;
var
 b, c : array [1..lastb] of byte;

procedure PerfectShuffle; // Perfect shuffle
var
 i : integer;

begin
 if (lastb mod 2) = 0 // only if is a even number of bytes!
 then
 begin
 for i := 1 to (lastb div 2) do
 c[i*2-1] := b[i];
 for i := (lastb div 2)+1 to lastb do
 c[i*2-lastb] := b[i];

 for i := 1 to lastb do
 b[i] := c[i];
 end;