(Message perl/qotw/discuss:517) /home/mjd/bin/mailpager 517 Received: (qmail 28577 invoked by alias); 11 Nov 2002 13:45:05 -0000 Mailing-List: contact perl-qotw-discuss-help@plover.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Digest-Subscribe: List-URL: Delivered-To: mailing list perl-qotw-discuss@plover.com Received: (qmail 28568 invoked from network); 11 Nov 2002 13:45:05 -0000 Date: Mon, 11 Nov 2002 08:37:20 -0500 From: John Macdonald To: perl-qotw-discuss@plover.com Subject: An unproven expert solution approach Message-ID: <20021111083720.E2445@algate.perlwolf.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.3.22.1i I haven't had to time to work on this at all, I'm afraid, but the approach I would have tried has only been partly expressed in the discussion I've seen. (It may have been fully done in some of the code - I didn't read much of that.) What I planned to do was: for each character position in string1 find each matching character in string2 and determine the maximum length common substring (starting from those positions) Take the resulting data structure and treat it as a dynamic programming problem to choose which of the common substrings (or shorter) can add up to both strings. However, it's been a few decades since I last had to look at a dynamic programming problem - I suspect that it might require some modifications to account for the fact that a partial answer includes multiple possibilities (you need to track the best possible partial solution for each combination of choosing the required letters from the second string). This technique would get slower for anagrams that contained many duplicate letters.