Re: given Dict=(act, eat, sat, ...) make a long chain (no repeats) with 2-letter overlaps

On 6/17/2024 4:24 PM, James Waldby wrote:

In sci.math HenHanna <HenHanna@devnull.tb> wrote:

given (a list of 3-letter words)
   Dict=(act, ATT, eat, sat, sit, cat, bat, dog, god, mat, tim, kim, ...)
>
The object is to make a long chain (no repeats) with 2-letter overlaps.
>
                               e.g. -- [cat, ate, tea, eat, ATT, ...]
>
What's a good approach (in Python)?

 According to ref 1, longest-path problems are NP-complete.  At the
moment there's no method known that is "good" in general for the
problem.  However, if all of the dictionary words are chosen from a
natural-language, then we have a special (not general) case.  I think
in this special case a method like finding pairs, then combining pairs
to triple, then triples to fives, fives to nines, etc, might work
well, given obvious fallbacks to combining different-length sequences
when at some length same-length combinations don't exist.
 *Ref 1 <https://en.wikipedia.org/wiki/Longest_path_problem#NP-hardness>
*Ref 2 <https://en.wikipedia.org/wiki/NP-completeness>
 

>
              in Mathematica, it's easy to find   THE Longest    chain?
>
                             is this a typical NP-complete problem?

 As noted in ref 2, "A problem p in NP is NP-complete if every other
problem in NP can be transformed (or reduced) into p in polynomial
time", so there is a sense in which every NP-complete problem is a
typical NP-complete problem.
 

________________
>
-- Martha has aspirin in industrial allotments.
>
-- Two women enter erotic icehouse, seduce celibate teacher.
>
-- Rush showed editorial alarmism, smeared educational alliance ceaselessly.

thanks!
word Chain    with 3-letter overlaps (between successive words)
10 (shtoomest, estrayed, yedo, edomitish,
                               ish, ishime, imelle, ller, lerps, rps)