Save permutation with less bytes than permutation length

0
votes

I want to save a permutation of the length N in less than N Bytes. The permutation of length N has the elements 1,2,3,....,N.

The permutation has following preferences:

Additional reading: Rank and unrank permutation with special properties

Is there a way to combine these preferences to minimize the possible permutations to rank? Or are there more preferences which can be used to describe the permutation in less Bytes than it is long?

My idea was to specify a subset of permutations and then Rank it, but iam failing to combine the preferences to create one subset defined through the preferences.

1
arraysalgorithmcompressionpermutationranking
For a start, you could save it in (n-1) bytes. You could store the first n-1 elements. The last one is implied - Abhay Aravinda
The problem description is a little vague. It could be improved by adding a detailed description to each of the bullet items. An example would also help. - user3386109
@AbhayAravinda and the second to last one has only 2 possibilities and could be stored in 1 bit, etc, eventually the whole permutation can be encoded using its index in the factoradic number system. That doesn't use the special properties though. - harold
What is a DI sequence? What is strength? - templatetypedef
Updated description - TTho Einthausend

1 Answers

1
votes

In general, no.

Permutations of length n with only one cycle are in 1-1 correspondence with permutations of length n-1.

The strength is a positive integer between that cannot exceed n^2.

The number of possible bitstrings is 2^(n-1).

By the pigeon principle, for some bitstring and some strength there must be at least (n-1)! / (2^(n-1) n^2) = n! / (2^(n-1) n^3).

From Stirling's approximation we can see that

log2( n! / (2^(n-1) n^3) )
    = n log2(n) - n log2(e) + O(log2(n)) - (n-1) - 3 log2(n)
    = n log2(n) - n (log2(e) + 1) - O(log2(n))
    = n log2(n) + O(n)

Which tells us that the number of bits needed, even with your conditions, grows faster than linear. So for large enough n, you will need more than n bytes of data to specify a single permutation.