XPost: comp.lang.python, sci.math   
   From: no@no.no   
      
   In sci.math HenHanna  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    
   *Ref 2    
      
   >   
   >              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.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)