0
$\begingroup$

Suppose we are tasked with expressing a randomized list of all numbers up to but excluding $2^n$ (ie. a random list of all n-bit numbers). What are some efficient ways to do such a listing using as few bits as possible?

Attempt: My thought is that the verbose listing of all $n$-bit numbers has a lot of redundancy, so if we start by listing all $2^n$ numbers, $2^{n-1}$ of those numbers will have a number that is identical except for one bit (that has been previously listed)––so we can drop the $n^{th}$ bit of those $2^{n-1}$ numbers. Now among that same set of $2^{n-1}$ numbers, there will be $2^{n-2}$ values that will have a number that is identical until the last two bits, so we can drop the $n-1^{th}$ bit of those $2^{n-2}$ numbers as well. Continuing on iteratively, we can find $2^{n-k}$ numbers that can have the final bit dropped, with $k=1,2,3,4,...n$. Finally, there is one number that can be eliminated entirely (intuitively, this makes sense because the last number in a known set can always be determined if we know all others).

Here is an example that lists all 3-bit numbers (in increasing order):

  • 000
  • 00
  • 010
  • 0
  • 100
  • 10
  • 110
  • .

It seems like we can model the number of bits this method uses as such: $$2^{n-1}n + 2^{n-2}(n-1) + ... + 2^1(2) + 2^{0}(1) = \sum_{k=0}^{n-1} 2^k(k+1) = 2^n(n-1)+1$$

(saving $2^n -1$ bits from the verbose $2^n*n$ version)

$\endgroup$
  • $\begingroup$ Is the output format required to be list of bits or could it be a higher level description? The input is ordered list or only number of bits? Would LFSR with added 0 (here $n$ zeros) be a valid solution? $\endgroup$ – Evil Feb 22 '17 at 2:56
  • $\begingroup$ I'm not sure what you mean by a "higher level description"–but, for example, hexadecimal would not be allowed. $\endgroup$ – David C Feb 22 '17 at 2:59
  • 1
    $\begingroup$ If the order is predetermined and arbitrary, you need $\lceil \log_2 2^n! \rceil$ bits to describe it. $\endgroup$ – Yuval Filmus Feb 22 '17 at 3:03
  • $\begingroup$ You can encode a permutation on $m$ values using a number in the range $0,\ldots,m!-1$ in many different ways. It's a nice exercise. You can think of this number from $0,\ldots,m!-1$ as encoding a number from $0,\ldots,m-1$, a number from $0,\ldots,m-2$, ..., and a number from $0,\ldots,0$. $\endgroup$ – Yuval Filmus Feb 22 '17 at 3:12
  • 1
    $\begingroup$ Can you clarify your question? I'm not sure I understand it. What do you mean by "do such a listing using as few bits as possible"? Are you really just looking for an efficient way to record a permutation of all $n$-bit words? $\endgroup$ – Yuval Filmus Feb 22 '17 at 12:12
2
$\begingroup$

Since $n$ is known from the start, you know that there are exactly $2^n!$ possible lists. Calculate the index of your list in a lexical ordering of all permutations, and then write that number using $\lceil log_2(2^n!)\rceil$ bits.

In practice, you can come arbitrarily close to this bound using arithmetic encoding, without having to manipulate very large integers.

$\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.