[CST-2] Kolmogorov complexity - cost of sorting

[Timothy Hospedales]

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