algorithmic problem

[gusl]

Given a set L of permutations of a list, compute the maximal partial order (DAG) under which all lists in L are topological sorts. How would you do this? Can you do better than O(m n^2 k^2)? (m = number of lists in L, k = # of things in domain = the size of the elements of L)
Sounds like an ILP problem.

One idea: whenever a cycle is detected, all the elements are deemed incomparable.

Comments

[bhudson.livejournal.com]

Store the complete graph, then mark edges as inconsistent. Then DAGify it (um... not clear on that one, but that seems easy enough?). Marking edges is n work per item, and there are mn items. *Plus* k^2, instead of *times* k^2 like in your thing. Still not exactly palatable.

[gustavolacerda.livejournal.com]

<< Marking edges is n work per item, >>

What is an "item"?

[gustavolacerda.livejournal.com]

<< Marking edges is n work per item, and there are mn items.>>
and there are k(k-1) edges to loop through.

[bhudson.livejournal.com]

An item is a thing, of which you have k in the universe, but only n in any given list.

You don't need to loop through the entire set of edges just to mark one, hence you have an additive rather than multiplicative dependence on k². O(mn²) to mark the edges, then another O(k²) to write out the edges that weren't marked.

Of course, what comes out isn't a DAG. We leave the final step as an exercise to the reader.

[gustavolacerda.livejournal.com]

<< You don't need to loop through the entire set of edges just to mark one >>

Sure. But you want to mark *all* edges, right?



<< Marking edges is n work per item, >>

are you marking *all edges* in O(nk)?

[bhudson.livejournal.com]

There is confusion here. Maybe you should try to parrot my algorithm and we can figure out if we at least agree on that.

[gustavolacerda.livejournal.com]

One vague idea:

* take the UNION of all the complete DAGs corresponding to each list
* find all cycles there. A, B in the same cycle => A, B in the same "set" (permutations between things in the same set are graph automorphisms of the final DAG)

[gustavolacerda.livejournal.com]

<< permutations between things in the same set are graph automorphisms of the final DAG >>

Therefore, all nodes in the same set have the same incoming and outgoing edges. This means we can collapse sets of nodes into "supernodes".
For the final DAG, you just make sure that there are no edges between members of the same set (and propagate each supernode's incoming and outgoing edges into all members... or you could just leave the final DAG in the supernode representation.

another idea

[gustavolacerda.livejournal.com]

sequence alignment

Re: another idea

[gustavolacerda.livejournal.com]

just like in diff.

[rdore.livejournal.com]

Your description is awful. I spent 10 minutes reading it and the comments over and over and I'm still not sure what the question is.

1. Use variables of some sort to denote things you're talk about
2. Don't call something a list unless its ordering is important

As far as I can tell you have:

A collection of k objects, let's call it X
A collection of linear orderings of subsets of X, which you call L

The size of L is m. Each linear ordering is on a subset of size n.

What you want to output is the maximum partial order of X which is a weaken of each element of L (on that element's domain).

If this is the right question, the answer is often not unique. For example, X={a,b,c} and L={[a,b],[a,c]}, then a maximal partial order will relate b and c in some way, but either way will do.

[gustavolacerda.livejournal.com]

<< then a maximal partial order will relate b and c in some way, but either way will do. >>

This will not happen if all lists in L are permutations of each other (as stated). I guess I should have noticed that k=n.

[rdore.livejournal.com]

Oh ok. Well suppressing log factors, I think the complexity is O(mk+k²). Make a graph on the k objects by throwing in all the consecutive pairs from all the lists. This is O(mk). Then detect all the strongly connected components - O(k²). Remove the edges of the strongly connected components - O(k²). Then take the transitive closure - I think this is O(k²) at least for a DAG, not sure.

[gustavolacerda.livejournal.com]

I think this post is a great example of how difficult mathematical communication is. The people exposing want to take shortcuts, while the people listening want to be completely clear on what everything means (but they don't share the language used in the shortcuts). It's very hard to put oneself in the other person's shoes.

[bhudson.livejournal.com]

It seemed clear enough to me -- definitely well out of the realm of awful. I guess it is my bread and butter to work these things out.

[rdore.livejournal.com]

It wasn't the technical terms that confused me, it was the less technical ones. Using "a list" to refer to two completely different things in the space of about eight words was the biggest problem. Also the fact that n and k were used to refer to the same quantity.

[bhudson.livejournal.com]

For a good time, man perldsc.