Sort by typical position?

Question

Lets say, we have a lot of lists (sequences of variable length) of some limited set of elements:

[A, B, D, E, Q], [A, D], [A, C, E, F, G, H, Y, Z], [B, A, E, D, Z, Y], ...

The problem is to get the single order, based on "how typical" some position is, eg, in our case it can be (coincidence with alphabetical order is just a coincidence):

[A, B, C, D, E, F, G, H, Q, Y, Z]

But lets say [Z, Q, Y, C, B, A, D, E, F, G] is "surprising" order, far from being "typical".

The questions are:

• are there any "official" CS terms for the situation (so I can do further searches)?
• what are practically popular definitions / metrics for "how typical" (or "surprising") in the above description?

My idea so far is to count "average position", normalized to the max length of the list. Then the order will be by increasing normalized average positions. I feel, maybe term rank and some statistics' techniques are also applicable to this, but I am more interested in some easily (one pass) computable metrics. Any pointers?

One more idea is to calculate probability of every pair where one element is before another, and sort based on whether probability is less than 0.5 or more. But this may need a triangular matrix and a lot of computations. (For the example above, p(A before D|both occur) = 1, but p(A before B) = 0.5).

One gotcha may be that is some element is usual for the beginnings and ends, but never the middle, the average result may still be in the middle... But I guess it may be too subtle to satisfy.

For now, using very rough method:

def approx_position(position, length, master_length):
    return int(position * master_length / float(length))

seqs = ['A', 'B', 'D', 'E', 'Q'], ['A', 'D'], \
    ['A', 'C', 'E', 'F', 'G', 'H', 'Y', 'Z'], ['B', 'A', 'E', 'D', 'Z', 'Y']

master = []
for s in seqs:
    total = len(s)
    est_len = len(set(master) | set(s))
    for i, item in enumerate(s):
        if item not in master:
            new_pos = approx_position(i, total, est_len)
            master.insert(new_pos, item)

print master
# ['A', 'C', 'B', 'D', 'F', 'G', 'H', 'E', 'Y', 'Z', 'Q']
# when seqs in reversed order:
# ['B', 'C', 'A', 'F', 'E', 'G', 'H', 'D', 'Q', 'Z', 'Y']

NB. Python insert works on intervals between list elements. So 0 corresponds to the place before first element.

Not ideal, but at least almost one pass (one hidden pass in set union).

Something similar is for example discussed here: https://stackoverflow.com/questions/4645874/merging-some-sorted-lists-with-unknown-order-sequence However, my problem is overdetermined, so the question is how to do relaxation, while the results are still near optimal (the criteria is part of the answer).

(trying to widen my horizons as it is usually hard to find a right term for something if one has never encountered that term before)

Answer 1

As I understand your question, your problem statement is:

Given a set of ordered lists $\{L_1,L_2,\ldots,L_n\}$, learn the relation $r(a,b)$ for the partial order of each $L_1,L_2,\ldots,L_n$. Then use this learned relation to sort a new list.

So, in your example, the relation would be the lexicographical order. But your data set has some noise because the last list breaks the order in several places.

This seems to be a case of preferrence learning, and more specifically, object ranking.

Answer 2

The problem of sorting elements given some approximately sorted samples is difficult. There is a similar problem called ranked voting (not a CS term, sorry). It is simpler in two important aspects - all of the lists given contain all of the elements each, and we are only interested in the top few slots rather than the entire list. Your proposed method is equivalent to the Borda count method.

However, if you are only interested in finding surprising orderings, you can do it by computing the average disagreement between each pair of lists. As for the disagreement between two lists, I propose counting the number of pairs of elements that exist in both lists and whose relative order differs. For example ABCD and DCBA have six conflicting pairs while ABCD and FEDC only have one.