[comp.lang.pascal] Anagram

sbarnhar%MAILBOX.MAIL.UMN.EDU@uga.cc.uga.edu ( Shawn Barnhart) (01/03/91)

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
algrotithms"-type books, but none mentioned algorithms for variable-length
(or any length, for that matter) anagrams.   I know this sounds like a tedious
CSci assignment, but ever since I saw my first issue of _Spy_ and their
"Monthly Anagram Analysis" I've had the burning desire to find them the brute
force way.  Reply here or to Email.  Gracias.

----------------------------------------------------------------
If you didn't get caught, how do you know that you did it?

sbarnhar@mailbox.mail.umn.edu
----------------------------------------------------------------

eli@smectos.gang.umass.edu (Eli Brandt) (01/05/91)

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

PHARMAIL%RUG.NL@uga.cc.uga.edu (01/08/91)

{
Hi netlanders,
some time ago, while studying recursion, I made the following program
in Turbo Pascal. Recursion is great!
I think it produces anagrams.
What kind of magazine is _SPY_? Never heard of it.
Please let me know.
Greetings, Paul
}

program anagram;
{
  recursive calculation of permutations
  Author: Paul B. van den Berg - PHARMAIL@rc.rug.nl
}

const
 maxL = 8;
type
 charray = string[maxL];
var
 st: charray;
 count: longint;
 n: integer;
 ch: char;

procedure permutate(x: integer; var st: charray);
 var i, j: integer; st2: charray;
begin
 if x=1 then
 begin
  inc(count); write(' ',st)
 end
 else
 begin
  dec(x); j:=n-x;
  if x=2 then writeln;
  permutate(x,st);
  for i:=j+1 to n do
  begin
   st2:=st; ch:=st2[j]; st2[j]:=st[i]; st2[i]:=ch; permutate(x,st2)
  end
 end
end;

begin
 writeln(' RECURSIVE CALCULATION of PERMUTATIONS ');
 writeln;
 write('Input some string (max ',maxL,' letters): '); readln(st);
 count:=0;
 n:=length(st);
 permutate(n,st);
 writeln; writeln(count,' permutations');
end.

ECOAV%ECOSTAT.AAU.DK@uga.cc.uga.edu (01/09/91)

> 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
> algrotithms"-type books, but none mentioned algorithms for variable-length
> (or any length, for that matter) anagrams.   I know this sounds like a tedious
> CSci assignment, but ever since I saw my first issue of _Spy_ and their
> "Monthly Anagram Analysis" I've had the burning desire to find them the brute
> force way.  Reply here or to Email.  Gracias.

The following PASCAL program should do the job in an illustrative way:

program test(input,output);

const
   max_len = 10;

type
   string = varying [max_len] of char;
   check  = array [1..max_len] of boolean;

var
   flag         : check;
   line,anagram : string;
   ll,ptr       : integer;

procedure permute;

var
   i : integer;

begin
   if ptr>ll then begin
      writeln(anagram)
   end else begin
      for i:=1 to ll do begin
         if flag[i] then begin
            anagram[ptr]:=line[i];
            flag[i]:=false;
            ptr:=ptr+1;
            permute;
            ptr:=ptr-1;
            flag[i]:=true;
         end;
      end;
   end;
end;

var
   i    : integer;

begin
   write('Enter string> ');
   readln(line);
   ll:=length(line);
   for i:=1 to ll do flag[i]:=true;
   anagram:=line;
   ptr:=1;
   permute;
end.

Note: This is VAX PASCAL. To convert to TURBO PASCAL substitute
      "varying [max_len] of char" with "string[max_len]".

                                                        Arne Vajhxj
                                                        ISIS08@ECOSTAT.AAU.DK

einstein@cs.mcgill.ca (Michael CHOWET) (01/10/91)

  Shawn Barnhart posted a little while ago for an anagram generator that is
not limited by size. Well, after thinking it over for a day or so, I came up
with the following.... (Note, this program was written in Turbo Pascal 
('natch :-), so caveat emptor. This makes use of the string type, and the 
length function for it. As well, this is only good for starting words where
the letters are all unique. If any letter appears twice, the exit condition
at the UNTIL would need to be substituted for a flag containing false if the
ENTIRE link array is void of True's. (Ie, For Ct := 1 to Length(S)-1 do 
Flag := Flag Or L[Ct] ; ) Enjoy...)

-------->CUT HERE-------->CUT HERE-------->CUT HERE-------->CUT HERE-------->

program Give_Anagrams ;

{Written: Jan 8th 1990   }
{By     : Michael Chowet }
{Note   : This code is freely distributable by anyone. I hereby relenquish }
{         it into the public domain... }

var
  s : string ;

procedure swap ( var ch1,ch2 : char ) ;
var temp : char ;

begin

  temp := ch1 ;
  ch1  := ch2 ;
  ch2  := temp;

end ;

procedure anagram ( s,s2 : string ) ;
var  i, ct : integer ;
     l     : array [ 1..3 ] of boolean ;

begin

  for i := 1 to length(s)-1 do
    l[i] := false ; { fill the link array with NOT-YET-SWITCHED flag }

  repeat

      i := 1 ; { start looking at the first letter pair }

      while (i<length(s)-1) and l[i] do
        i := i + 1 ; { move forward to first pair that are not yet switched }

      if not(i=length(s))then { iit's not off the array }
        begin

          swap ( s[i], s[i+1] ) ;         { switch your letters }
          for ct := 1 to i-1 do
           if l[ct] then l[ct] := false ; { turn N-Y-S flag on for pairs B4 }
          l[i] := not l[i] ;              { flip flag for the current pair }

        end ;

      writeln ( '====>',s ) ;

  until s=s2; {  this condition will need to be   }
              { changed for non-unique characters }

end;


begin
  s  := 'MIKE' ; { place your word for anagram-ing here }
  anagram ( s,s ) ;
end.



==============================================================================
Today's message was brought to you by the letter 'S', the number 6, and

  		    =====> Einstein@cs.mcgill.ca  <====
             =====> Mike CHOWET | McGill CSUS VP External <=====

			Post back soon, now y'hear...
==============================================================================