-1

Is it possible to compress the given random permutation of any integer using N*(lg(N) -1) bits? For example if N= 512, then it could be represented using 512 * 9 = 4608 bits and its optimal representation can be represented using 4096 bits total.

I have been given only these two information and now I need to figure out whether we can represent the random permutation of 512 using less than 4096 bits or not. Please help me to get any idea on that. Thanks.

user9340043
  • 7
  • Hint for solving that yourself: How many random permutations of 512 bit collections are there? More or less than $2^{4608}$? Can you uniquely represent more than $2^{4608}$ different things with only 4608 bits? – Nova Mar 10 '18 at 21:13
  • it is not 2^4608, it is 2^9=512. here I want to describe that a permutation of a consecutive sequence of numbers can be represented using N(log2(N)-1) bits, which is N bits fewer than the obvious representation using Nlog2(N) bits. – user9340043 Mar 10 '18 at 21:22
  • You need to rephrase the question. It's not very clear as to what you're asking. Is the integer, your integer = 512? Or is it the number of bits in some other integer? Or something else entirely? – Paul Uszak Mar 10 '18 at 23:23

1 Answers1

0

I took this question to mean a random permutation of $N$ "things".

A random permutation of the set $\{1,2,\ldots,N\}$ is a member of $S_N$, the symmetric group of $N$ elements. It is well known that there are $N!$ permutations of this set. Stirling's approximation gives $$ N!\sim \sqrt{2\pi N} (N/e)^N $$ or the upper bound $$ \log_2 N!\sim \frac{1}{2}\log_2(2 \pi)+N (\log_2(N)-\log_2(e))\leq 1.326 + N(\log_2 N-1.442)\leq N(\log_2 N-1) $$ on evaluating the relevant constants.

kodlu
  • 9,338
  • Is there anyway to use interpolation to compress these random permutations, as I have been told that low order polynomial interpolation can achieve this? Is it true? – user9340043 Mar 11 '18 at 01:41
  • In general, no, by information theoretic arguments. Need $\lceil \log K\rceil $ bits to represent $K$ objects. If you have a subclass of permutations, or if the distribution of the permutations is not uniform, compression on average (but not work case) is possible. – kodlu Mar 11 '18 at 02:04
  • But an interpolation over $N$ points would yield a degree $N-1$ polynomial except in special cases. – kodlu Mar 11 '18 at 02:07
  • Could you please provide me any example for that, so that I can write code for that? – user9340043 Mar 11 '18 at 02:10
  • For what exactly? Look up Lagrange interpolation formula. It is also used in secret sharing. – kodlu Mar 11 '18 at 02:19
  • How interpolation could be helpful for compression? I tries to google but couldn't find any example where we can compress an integer data from 1 to 100. Please help me to get an idea on that. – user9340043 Mar 11 '18 at 02:27
  • I told you it is NOT helpful in general, in my answer. – kodlu Mar 11 '18 at 02:34