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?

Advertisements

One response to “Redundant information in unordered lists: fundamental?

  1. It’s amazing in support of me to have a web page, which is helpful for
    my know-how. thanks admin

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: