Problems & Puzzles: Puzzles

 Puzzle 896. Optimal packing of a set of integers Here we ask for an algorithm that produces an optimal answer. The original problem goes back up to 1979 (See Ref 3). But in this puzzle I use a numerical version of it. Problem. "Given a set of decimal integers, what is the shortest string S of L decimal digits that contains all the integers as subsequences in the asked string."  Example: Set of integers: {123, 451, 46733} Optimal string:  S = 46751233, L = 8. Usually there are several distinct strings S with the same L minimal value. Regarding the asked algorithm remember that we ask here for the optimal solution, that is to say, the minimal L for the S asked solution. There are some other very simple algorithm & solutions, but these are not the optimal asked ones: a) The worst solution LWS, is just to concatenate all the integers of the set. For this solution L is the sum of the lengths of all the integers. b) A better solution LBS is to sum the counts of the distinct digits in each position of the integers. In this case, L is the sum of all the counts. But none of these algorithms produce the optimal solution LOS, as you soon will discover. Going back to the example shown above, LWS = 3+3+5 = 11, LBS = 2+3+3+1+1 = 10 but LOS = 8. OK. Hands to work! Let's define three sets: Set A: {4242064951, 5519385407, 6886477529, 3816749731, 4700006089, 9650560979, 4371455527, 5419320281, 8761823531, 3454277693} Set B: {Prime numbers from 2 to 97} Set C: {Prime numbers from 2 to 997} Q1. Develop and send your algorithm description. Q2. Send your best string S solutions for Sets A, B & C, respectively, as produced by your algorithm. [Starting point: my best solutions are L=45, 11, 21 for sets A, B & C, respectively] References: PLANET PACKING by A. ROSS ECKLER (2001) PLANET PACKING REVISITED by DANA RICHARDS (2001) Computers and Intractability: A Guide to the Theory of NP-Completeness, by Michael Garey and David S. Johnson. Appendix A4.2, SR8, Shortest Common Super sequence.

 Records   |  Conjectures  |  Problems  |  Puzzles

 Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.