2
$\begingroup$

For a given positive number n. Numbers from 0 up to n, are streamed one by one in some order without repetition.

What would be recommended a strategy to store the order of these n numbers in the most space conservative way?

Highest priority is to consume minimal bits to store the order. Second highest priority is to have minimal effort in adding the incoming number to the current order Least priority is the computational complexity in retrieving the order.

Retrieval will be done only when all n numbers have been added.

Deletion operation will not be performed.

Improve this question
$\endgroup$
  • $\begingroup$ The first and most trivial trick you should consider is, if n is known (or is communicated/stored before the sequence), then use only ceil(lg(n)) bits per value, rather than a standard CPU word. Everything else (compression-wise) relies on your assumptions for your likely sequences -- which are already quite specific since you expect each number to appear exactly(?) once. For instance, after sending the first k values, your domain has only n-k possible values, which require fewer bits to encode. $\endgroup$ – Omar Jun 24 '17 at 21:46
  • $\begingroup$ @Evil, sending/storing the permutation index sounds interesting to me. That said, wouldn't that require O(log(n!)) = O(n log n) bits? Unless the constants are significantly better, that sounds similar to sending n values each with log(n) bits (i.e., the default method)? What am I missing? $\endgroup$ – Omar Jun 24 '17 at 21:57
2
$\begingroup$

Given that all the numbers form 0 to N-1 are to be stored, and their order, there will be N! permutations. The minimum number of bits needed to store any combination and its order from an randomly selected order will be

$$\lceil \frac{\log(n!)}{\log(2)}\rceil$$

For example give a range of {0..99} (N=100) the Number of bits to store the permutations is $\lceil \frac{\log(100!)}{\log(2)}\rceil = 525\text{bits}$.

This can be encoded using a Mixed-Radix Calculation, or can be done using Arithmetic Coding (with a slight extra few bits).

In short using a LIST of the numbers to choose from. Each time one of the numbers is eliminated, to take the last number in the list, move it to fill in the eliminated number, adjust the "stats" for Arithmetic coding. Since All the symbols are equally, the same percent applies to all the symbols, and makes easy and Linear time to encode.

Each elimination increase percent chance of the next symbol (IE Number) occurring in the remaining of the list using list of the 0..(N-1) and using the move the last item to the empty position, and shorten the list.

A hash table can be used to make finding the number to replace be done in $\mathcal O(1)$ expected time, for the $\mathcal O(N)$ sequence.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.