2 ms·

You have N elements, so they have N! possible permutations. The ordering of the list is one such permutation; to describe one message out of a language of N! po

by uvdiv 14y ago

You have N elements, so they have N! possible permutations. The ordering of the list is one such permutation; to describe one message out of a language of N! possible messages, it takes lg(N!) bits.

dpark 14y ago
Interesting. Thanks for explaining. Are there ways to store (multi)sets that take advantage of this fact to reduce size? I can't envision a way to utilize this information meaningfully. It seems like any storage scheme would imply some ordering.
- uvdiv 14y ago
  Yes, the other commenter ChuckMcM showed one https://news.ycombinator.com/item?id=4680259 https://news.ycombinator.com/item?id=4680259 An ordering of a storage scheme doesn't always store information. E.g. if the list is sorted, the ordering is completely determined by the data -- it's redundant. For storing integers, an idea to is store the pairwise differences between sorted elements. E.g. [30,10,20] -> [10-0,20-10,30-20] = [10,10,10]. If you have N integers of typical size X, the differences will be much smaller, typically on the scale of X/N. With variable-width integers, X/N takes lg(N) fewer bits to encode than X. So you save N lg(N) bits (asymptotically the same as lg(N!)), compared to storing the integers literally.
  - dpark 14y ago
    > Yes, the other commenter ChuckMcM showed one I saw that comment. I'm not clear how that's not still storing ordered data, or rather how the order there is not storing information. Obviously my information theory knowledge is weak. > if the list is sorted, the ordering is completely determined by the data -- it's redundant. I don't understand this. In what way is the information redundant? If there's 3.17 MB of data in the ordered list, and 2.2 MB of data in the ordering itself, the information stored in the ordering cannot be redundant, because that would mean >4.4MB of information is stored in the ordered list.

by uvdiv 14y ago

You have N elements, so they have N! possible permutations. The ordering of the list is one such permutation; to describe one message out of a language of N! possible messages, it takes lg(N!) bits.

dpark 14y ago

Interesting. Thanks for explaining. Are there ways to store (multi)sets that take advantage of this fact to reduce size? I can't envision a way to utilize this information meaningfully. It seems like any storage scheme would imply some ordering.

uvdiv 14y ago
Yes, the other commenter ChuckMcM showed one https://news.ycombinator.com/item?id=4680259 https://news.ycombinator.com/item?id=4680259 An ordering of a storage scheme doesn't always store information. E.g. if the list is sorted, the ordering is completely determined by the data -- it's redundant. For storing integers, an idea to is store the pairwise differences between sorted elements. E.g. [30,10,20] -> [10-0,20-10,30-20] = [10,10,10]. If you have N integers of typical size X, the differences will be much smaller, typically on the scale of X/N. With variable-width integers, X/N takes lg(N) fewer bits to encode than X. So you save N lg(N) bits (asymptotically the same as lg(N!)), compared to storing the integers literally.
- dpark 14y ago
  > Yes, the other commenter ChuckMcM showed one I saw that comment. I'm not clear how that's not still storing ordered data, or rather how the order there is not storing information. Obviously my information theory knowledge is weak. > if the list is sorted, the ordering is completely determined by the data -- it's redundant. I don't understand this. In what way is the information redundant? If there's 3.17 MB of data in the ordered list, and 2.2 MB of data in the ordering itself, the information stored in the ordering cannot be redundant, because that would mean >4.4MB of information is stored in the ordered list.