Suppose we are asked to list all $n$-bit numbers in an order that is predetermined and random.  What is the most efficient way to  do such a listing using as few bits as possible?Attempt: Start by listing all $2^n$ numbers.  $2^{n-1}$ of those numbers will have a predecessor that is identical until the last bitso 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 set of predecessors that are identical until the last two bits, so we can drop the $n-1^{th}$ bit of $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=3,4,...n$. The final number needs zero bits to be determined.  Here is an example list with all 3-bit numbers in increasing orderwe can infer the missing bits by referencing numbers that are listed previously, and because we know it is a complete permutation:00000010010010110.In general we use the following number of bits in this method of representation:$$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 complete list)
Most Efficient Way to List All $n$-bit Permutations
efficiency;permutations;storage
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. 