[CST-2] Kolmogorov complexity - cost of sorting

[Alan Lawrence]

In that case all you've got is that each number must be more than the 
previous one, which is a slight decrease in entropy but no, not a lot. 
You could make a saving by only storing the differences between 
successive elements (as unsigned floats), perhaps.

--Alan

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

> But what if its not a reordering of 1....N, presumably the unsorted
> numbers could be a random bunch of N floats, the longest of which
> takes log N bits to represent. I dont see how that bunch of floats
> being sorted makes them any more compact to represent since you now
> cant depend on there being unit/constant space between each.
>
> Tim
>
>> 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
>>
>>
>>
>> _______________________________________________
>> 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