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

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)

• 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?
– Evil
Commented Feb 22, 2017 at 2:56
• I'm not sure what you mean by a "higher level description"–but, for example, hexadecimal would not be allowed. Commented Feb 22, 2017 at 2:59
• If the order is predetermined and arbitrary, you need $\lceil \log_2 2^n! \rceil$ bits to describe it. Commented Feb 22, 2017 at 3:03
• 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$. Commented Feb 22, 2017 at 3:12
• 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? Commented Feb 22, 2017 at 12:12

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.