I am replying to myself to thank all the Perl mongers who replied with help. Indeed, my problem is topological sort, as stated by Alex Vandiver and Gyepi SAM. I did not see that because the input format is different from that required by the Unix tsort program.
A search for: tsort "perl power tools" found this http://search.cpan.org/src/CWEST/ppt-0.14/html/commands/tsort/index.html which leads directly to the perl code I used this to solve the problem. Note the strange name -- tcsort not tsort. (Perhaps in homage to Tom Christiansen, the prime mover of the very useful but moribund ppt project.) I earlier found tsort.exe (port to Windows) inside coreutils-5.3.0-bin.zip at http://sourceforge.net/project/showfiles.php?group_id=23617&package_id=1 42775 Unfortunately this tsort.exe depends on libintl3.dll which was not in the *.zip file and which I could not find anywhere. Aside: Does anyone know where I can get a libintl3.dll ? Both versions of tsort require the 2 values on each input row be separated by one space. Fortunately I was able to transform my data into this format. Major kudos to Ben Tilly! He wrote from scratch a perl program that solved the problem. (Since he put in the effort to write this I took some extra time to test it. It produced the same output as tsort, because the lists overlapped enough to overcome the fact that the output order is in general not deterministic.) I think the problem statement I gave was clear enough. Any cycle in the input is an error. The tsort program in perl simply reports "cycle detected" without any information as to which elements are on the cycle. My use was not related to alignment of DNA. It was part of a personal mashup to combine data about cars that I scraped from e.g. http://autos.yahoo.com/toyota_camry_se_v6-specs/?p=all The actual values in the list are strings such as these: Cylinders Horsepower @ RPM Fuel Economy Cty/Hwy As another aside, if people are interested I can send 77 lines of data for each of these 2008 model year cars: Camry, Accord, Infiniti_G35, Impreza, Altima, Audi_A4, Volvo_S40, Saab_9_3 I would not mind off-list opinions on any of these cars. In general I want a car with width <= 70.7 inches (the Accord at 71.7" is probably too wide to fit in my garage), and would like AWD. Thanks, Steve -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Tolkin, Steve Sent: Tuesday, January 29, 2008 12:12 PM To: Boston Perl Mongers Subject: [Boston.pm] merging lists that are ordered but not sorted I am looking for a perl program that will solve the following problem. Suppose I have 2 or more lists that are (conceptually) sublists of the same underlying list. I want to reconstruct the underlying list. In other words the order of the elements agrees in all the lists, but there is no sort condition. Example: List 1: dog, cat, mouse List 2: dog, shark, mouse, elephant There are 2 possible outputs, and I do not care which one I get. The reason that I have not just coded this up is that it seems it require an unbounded amount of look ahead. Also, when there are more than 2 lists, I think I need to read from all of them before making a decision about which element can be safely output. Thanks, Steve -- Steven Tolkin [EMAIL PROTECTED] 508-787-9006 Fidelity Investments 400 Puritan Way M3B Marlborough MA 01752 There is nothing so practical as a good theory. Comments are by me, not Fidelity Investments, its subsidiaries or affiliates. _______________________________________________ Boston-pm mailing list [email protected] http://mail.pm.org/mailman/listinfo/boston-pm _______________________________________________ Boston-pm mailing list [email protected] http://mail.pm.org/mailman/listinfo/boston-pm
