Most Efficient Way to List All $n$-bit Permutations

Question

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)

Answer 1

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.