Ok, so you don’t want to just compress a permutation, what is trivial to do in practically optimal way (using lg(n!) bits), but at cost of requirement of complete decoding to access the values.

You want a compressed data structure: store compressed permutations in memory, still having relatively quick random access: be able to ask pi(i) type of questions.

This seems an artificial problem: directly writing the pi function is n lg(n) bits. It is 25% more than optimum (lg(n!)) for n=128, 17% more for n=1024. It doesn’t seem worth fighting for (?): just hold compressed at a medium, but decompress while in memory (unless small n).

However, generally I completely agree that compressed data structures, like succinct tree, is an important field of research … it is also very hard. But the real problem with lack of research there is that data compression is no longer a sexy topic at academia, no funding … I know a few dozens of specialists in quantum information theory in Poland, which probably will never be really applied … but sadly nearly no specialists in classical information theory: the one used literally everywhere.