Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you have a set of 4 elements {A,B,C,D}, but without specifying their order. Now, if you want to specify which precedes which, that would mean you need to provide more information.

But at the same time, writing down the ordered list {B,C,A,D} doesn't take more text. That's probably because order is implicit when writing down things, even when I say that {A,B,C,D} is unordered, the way I write it down has order, I just tell you to ignore it.

So which is true? Does order carry additional information, and if so, why don't ordered lists take more text to describe than unordered ones?

share|improve this question
    
See How to define the entropy of a list of numbers? -- perhaps not exactly a duplicate but close. –  joriki Jan 7 '12 at 14:45
    
my address is $\{3412\}$ $\{ifstr\}$ street –  yoyo Jan 7 '12 at 15:42
add comment

1 Answer

up vote 5 down vote accepted

Ordered lists do contain more information.

Precisely, you can order $n$ elements in $n!$ different ways, so say you got $4$ elements ${A,B,C,D}$ with no order defined. When writing them down in a particular order, the order itself defines a number from $0$ to $4! = 23$, so you basically stored $log_2 24$ additional bits.

Now when you write down unordered elements, you'll of course need to choose some order (which is "waste" information in that moment). But if you choose a particular order, you can use this to store additional information in the same message. This is actually a neat trick in steganography, i.e. sending hidden messages, in data where order is of no importance (HTML attribues are great!).

On the other hand, if order does matter, you cannot afterwards rearrange the items to store extra information or the original order is lost.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.