You want to implement some kind of topological sort.

Every time an item A occurs before an item B in one of your sublists, that is a constraint that A must occur before B in the global list. So add the edge A->B to your graph.

Now, you can do several things to your graph. If it has a cycle, you can give an error. Otherwise you can perform a topological sort using your favorite algorithm or graph library. This gives an ordering of the vertices that is consistent with the meaning of each of these A->B constraints.

If you want to know if there is more than one topological sort possible, you can do something similar to what I outlined here. Just rank the vertices in the same way as I described. Suppose there are N vertices in your graph. If at the end of this process you have N ranks, then there's only one topological ordering possible. Otherwise, some rank must have more than one vertex, and the graph has more than one valid topological ordering.

It looks like Graph.pm does everything you need except for testing for multiple topological sorts. But along with the simple algorithm I outlined for that, you should be pointed in the right direction.

Update: It just occured to me that my "ranking" procedure in fact gives a topological sort (indirectly). Just list the things in order of rank. Within ranks, you can assign the order arbitrarily. If there's a cycle, you will fail in the first step (finding rank-0 nodes).

blokhead

In reply to Re: Reconstructing List Order From Partial Subsets by blokhead
in thread Reconstructing List Order From Partial Subsets by QM

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.