I completely agree compressing sets and multisets has known solutions. Once you drop the ordering information, it degrades into a delta+statistical encoding problem. I’m not particularly worried about that research in that area; ignoring ordering is easy.

Your Kth encoding sounds similar to Ordinal form (http://goo.gl/QjOKqy); which yes, does _some_ compression, but levels off at around 5%-8% savings once you get into larger permutations. So yes, possible, but also not impressive. Barbay (http://arxiv.org/abs/1108.4408) states that you can get smaller; but this requires valid SMUS and SUS cycles in the set. Sadly not enough shuffles fall into this ordering (http://users.encs.concordia.ca/~ta_ahmed/rc_camera_ready.pdf). Also, their research focuses on in-memory succinct form and the researchers neglect to mention how to serialize that information to a stream properly (or maybe they have, and I keep missing that discussion).

So yes, completely possible, but IMHO not good enough. Once we can start to break the 30%-50% savings for permutations, we can unlock some amazing opportunities in data compression space.