Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!spool2.mu.edu!samsung!ernie.viewlogic.com!m2c!umvlsi!dime!smectos!eli
From: eli@smectos.gang.umass.edu (Eli Brandt)
Newsgroups: comp.lang.pascal
Subject: Re: Anagram
Message-ID: <24639@dime.cs.umass.edu>
Date: 4 Jan 91 20:46:32 GMT
References: <25369@adm.brl.mil>
Sender: news@dime.cs.umass.edu
Reply-To: eli@smectos.CS.UMASS.EDU (Eli Brandt)
Organization: University of Massachusetts, Amherst
Lines: 18

In article <25369@adm.brl.mil> sbarnhar%MAILBOX.MAIL.UMN.EDU@uga.cc.uga.edu ( Shawn Barnhart) writes:
>Does anyone know of or know where I could find an algorithm for producing a
>complete set of anagrams for for any string of length N?  It seems (to my
>nonscientific mind) that the algorithm changes as more letters are added.  I was
>
>able to produce one that worked for 3 and 4 letter strings, but after that it
>broke down.  The bookstore here on campus had a smattering of CSci "101

Well, if you're not concerned with performance, the trivial recursive algorithm:

  anagrams(N-string) = 
     for all characters C in string: C concat all anagrams(N-string without C)

In the real world, you would want to derecursify this and, assuming you're going
to run your near-infinite mess through a dictionary, clip off impossible
word-beginnings (like "QKL") without evaluating the whole tree.

Eli