Redundant information in unordered lists: fundamental?

Let’s say you have an list of items, in some specific ordering: the list of your friends [james, tom, harry], say, in order of age.  The way I see it, there are two “types” of information here: the list items, and the list order.

Now, let’s say you want to make a list of specific “friendships”: [(eegg, james), (eegg, tom), (eegg, harry), (james, tom), (tom, harry)].  Now, there are several ‘orderings’ in this list that could be used to convey information: the order in which you list the friendships, and the order in which you list the two friends in each 2-tuple.

But what information can you convey using these orderings?  When specifying a friendship between two people, can you identify two “roles” played there?  Answer: no.

So you decide that you want to specify those friendships without putting any information in those orderings.  As you have many friends and space is at a premium, you also decide that you want to compress that data to “squeeze out” the wasted data that is taken up by the arbitrary order in which everything is specified.  Open question: how do you go about this?

Or to put the question a little more mathematically/computer-sciencey: what is the most spacially efficient way of serializing an arbitrary unordered set of items?

Advertisement