An efficient representation for permutations

摘要

We give a representation for permutations and we compare it with other representations. On average, our representation has lower entropy and it could be used to efficiently compress permutations. The comparison of the methods used for encoding permutations is done taking into account randomly generated permutations of order n, therefore the method would give good performance when every permutation is equally likely to be used as input for the compression (encoding) algorithm. For smaller values of n, we were able to draw the same conclusion for all permutations of order n: our representation gives better (lower) average entropy than other representations.