[CST-2] Kolmogorov complexity - cost of sorting

[Alan Lawrence]

Because you (or the decompressor) knows it's a permutation, i.e. some 
reordering of (1...N). Which is why it takes ~~log(N) space for each, as 
the numbers must range up to N.

--Alan

On Friday, May 31, 2002, at 08:22  pm, Timothy Hospedales wrote:

> Sounds sensible. But how do you actually use the lack of information
> it the sorted sequence to compress it to zero size? It doesnt seem
> like you can because you still have to know what particular numbers
> the sorted numbers were in order to put them back into their original
> unordered form. Which you cant do from zero size by the counting
> argument.
>
> Tim
>
>
>> It contains less information as it has fewer degrees of freedom?
>>
>> i.e. it's confined to be monotonically increasing/decreasing  across 
>> it's
>> length.
>>
>> log_2{n!} is the information content of a random sequence of length n
>> (it has n! possible orderings, so can communicate log_s{n!} bits of
>> information), the sorted version has 1 possible ordering, so conveys 0
>> bits)
>>
>>
>> --
>> David Singleton    _________________      St John's College, Cambridge
>>  C5 3rd Crt        +44(0)7980 641608   http://www.davidsingleton.co.uk/
>> !!my @cam.ac.uk address stops mid-June - use 
>> davidsingleton@cantab.net!!
>>
>>
>>
>> _______________________________________________
>> CST-2 mailing list
>> CST-2@srcf.ucam.org
>> http://www.srcf.ucam.org/mailman/listinfo/cst-2
>
>
> _______________________________________________
> CST-2 mailing list
> CST-2@srcf.ucam.org
> http://www.srcf.ucam.org/mailman/listinfo/cst-2