(* *** Nicholas Erho *** CMPT 141 ***** ID: 200613 *** October 13, 2004 *** Problem Restated: To find all the possible ordered combinations of a word or phase (aka an array of chars (aka a string)). Its important that a letter is never used more than once. INPUT : String OUTPUT : All the ordered combinations of the CHAR's of the String. PROCESS : Find all the ordered combinations. Problem Libraries: The library STextIO will be used to output user instuctions as well as the Char values of the strings that contain the found anagrams. This library will also be used to take the inital string from the user that is to be analyzed for anagrams and get other user interactions. The Strings library is used to find the length of the input string inorder so that the anagrams can be correctly found. Finally SWholeIO is used to print the string length as well as the number of anagrams on the screen. Problem Refinement 1: 1. Get input of string from user. 2. Process the anagrams using recursion. 3. Print out the anagrams. Problem Refinement 2: To find anagrams. Using a recursive procedure, each character of the anagram will have a point where it is a differnt character in respect to every other character. So if we were runing the string "abc" we would start off by setting the first value of the new anagrams to each one of the characters and then recurse the procedure and do the same thing for the next character until were at the string length. Then the full length of the new anagram will be printed and the branch of the recursion tree will close. eg. 1 2 3 <- recursion deepth. a([a][b][c]) -> Print close branch. a b([a][b][c]) -> Print close branch. c([a][b][c]) -> Print close branch. a([a][b][c]) -> Print close branch. b b([a][b][c]) -> Print close branch. c([a][b][c]) -> Print close branch. a([a][b][c]) -> Print close branch. c b([a][b][c]) -> Print close branch. c([a][b][c]) -> Print close branch. Problem Refinement 3: To find anagrams. Recursive Procedure. 1. If position char change at the last string spot Then a. Print the anagram 2. If position of char change not at the last string spot Then a. Loop: i. Through all the characters and put then in the next char position ii. Open the procedure again and do the same stuff. iii. Stick all of the anagram in the output string. b. Get the next position set up. Problem Refinement 4: Procedure for anagrams: If position = StringLength THEN If Length of Output String = StringLengthCon THEN Iff the anagram is of the right length: Print anagram string. End iff. Else do: Set a char value to Output[position] FOR Index = position to StringLength Set Output[position] value to Output[Index] Set Output[Index] to the char value specified before Run procedure again recusively. Set Output[Index] value to Output[position] End the FOR loop. Set Output[position] value to the char value End the procedure Program Refinement: Overall Procedures: 1. Anagram (Computes anagrams.) 2. QuickNumberOfAnagram (computes that number of anagrams using simple recursion.) 3. Header (Just used to display opening banner text.) Main 1. Display Header 2. Get the string that user wants to find anagrams of. 3. Tell the user the string length and the number of anagrams to be computed. 4. Ask the user if he still wants to continue (if not repeat except for header). 5. Use anagrams to compute the anagrams and display them. 6. Ask the user if they want to go again. Problem Data Table: * Type : String - ARRAY OF CHAR's * Vars : Input, Output - String StringLength, StringLengthCon, Number, length, position - CARDINAL Index - Integer Choice1, Choice2, ch - Char * Inports : STextIO -> ReadString, WriteString, WriteChar, SkipLine, WriteLn, ReadChar Strings -> Length SWholeIO -> WriteCard Sample IO: INPUT : Enter the word or line you wish to find anagrams of: hello OUTPUT : Length of the string is 5 characters and the number of possible combinations for these characters is 120. INPUT : Choice Do you wish to continue (Y/N)? y OUTPUT : Lots of numbered anagrams in 3 columbs (See "Sample Runs"). INPUT : Do you wish to run again (Y/N)? n User Manual: Description: This program is desgined to find all the anagrams or more specifically all the order combinations of the characters chosen. *"); WriteLn; Operation: To use this program if in M$ DOS type the name of the program from the directory that it is located. If in a GUI enviroment use the mouse to click on the icon that abstracts the program. Once Running follow the console prompt that askes you to input a string after a bannner is displayed. Banner looks like this: ************************************************************************ *** Nicholas Erho *** CMPT 141 ***** ID: 200613 *** October 13, 2004 *** ************************************************************************ * Anagram Finder * ************************************************************************ * This program is desgined to find all the anagrams or more * * specifically all the order combinations of the characters chosen. * * It is important to note that the numbers of possible combinations * * increases expedientially and consequently the time needed to find * * all the combinations. The number of characters is limited to 80 * * characters however any number of characters over 12 would take an * * enormous amount of time. * ************************************************************************ The prompt asking for a string should read: Enter the word or line you wish to find anagrams of: The string length that you entered and the number of anagrams will appear on the screen: Length of the string is # characters and the number of possible combinations for these characters is XXXX. (#: Number of characters in string, while XXXX is for the number of possible anagrams.) Its important that you dont use overly long strings of characters (more than 12 characters) because even though the program can handle strings up to 80 characters it will take a very long time because of the large number of anagrams needed to be computed. Because of this possibly long proccessing time you will be prompted and asked if you would like to continue: Do you wish to continue (Y/N)? X <- Your answer; 'y' if you want to run the anagram process with the given string or 'n' if you with to retype a string. Repeat as many times a needed until the number of anagrams is lower enough to be processed in a resonable amount of time (less than 20,000,000 anagrams). The Banner will only appear the first time. Next the anagrams will appear in 3 columbs with each anagram numberd in a similer fashion to this partial output for the string "hello": 1 : HELLO 2 : HELOL 3 : HELLO 4 : HELOL 5 : HEOLL 6 : HEOLL 7 : HLELO 8 : HLEOL 9 : HLLEO 10 : HLLOE 11 : HLOLE 12 : HLOEL 13 : HLLEO 14 : HLLOE 15 : HLELO When all the anagrams are finished being computed and displayed the prompt shown below will appear asking you if you wish to run the program again: Do you wish to run again (Y/N)? X <- Your answer; 'y' if you wish to run again and 'n' if you wish to quit. Repeat as many times a needed. However the Banner will only appear the first time. *) MODULE AnagramGen; FROM STextIO IMPORT ReadString, WriteString, WriteChar, SkipLine, WriteLn, ReadChar; FROM Strings IMPORT Length; FROM SWholeIO IMPORT WriteCard; TYPE String = ARRAY [0..80] OF CHAR; VAR (*Global Varible Declarations*) StringLengthCon, Number : CARDINAL; Input: String; (* Gets user string input*) Choice1, Choice2 : CHAR; (* Used in program flow user repeating decisions*) (*Simple Recursive Calculation that returns the number of ordered combinations*) PROCEDURE QuickCombNumber(length: CARDINAL):CARDINAL; BEGIN IF length = 0 THEN RETURN 1; (* Multiplies QuickCombNumber by one and ends the recursion.*) ELSE RETURN length * QuickCombNumber(length-1); (* from formula n! = n(n-1)! when n > 0 *) END END QuickCombNumber; (* Recursive Procedure that Calculats and prints out an anagrams of a string.*) PROCEDURE Anagrams(Output : String; position, StringLength :INTEGER); VAR (*Local Varible Declarations*) ch : CHAR; Index : INTEGER; OutIndex : CARDINAL; BEGIN (* Prints anagrams when position is at the end of the string *) IF (position = StringLength) THEN (* Checks to see if the possible anagram is the right length and prints then if it is*) IF ( Length(Output) = StringLengthCon) THEN INC(Number); (*Number used to keep track out the number of anagram outputs*) (*Writes Number in front of : to show that it is the number associated with the anagram*) WriteCard (Number, 8); WriteString(" : "); (* Runs through the string and outputs each char of the stirng, because WriteString allowed to be used for this purpose*) FOR OutIndex := 0 TO StringLengthCon DO WriteChar (CAP(Output[OutIndex])); END; IF ((Number MOD 3) = 0) THEN (* Causes the numbers and anagrams to print 3 per line*) WriteLn; END; END; ELSE ch := Output[position]; (* Marks output string position with char*) (*Runs through from position to string length changing string array values*) FOR Index := position TO StringLength DO Output[position] := Output[Index]; Output[Index] := ch; (* Initalize output string with the next character*) Anagrams(Output, position+1, StringLength); (*The anagram recursion happens here*) Output[Index] := Output[position]; (*Adds char to the output string to make anagram *) END; Output[position] := ch; (*Takes the marked output postion and restores it.*) END; END Anagrams; (* Ends procedure*) PROCEDURE Header; (* This procedure just displayes the header information*) BEGIN WriteString ("************************************************************************"); WriteLn; WriteString ("*** Nicholas Erho *** CMPT 141 ***** ID: 200613 *** October 13, 2004 ***"); WriteLn; WriteString ("************************************************************************"); WriteLn; WriteString ("* Anagram Finder *"); WriteLn; WriteString ("************************************************************************"); WriteLn; WriteString ("* This program is desgined to find all the anagrams or more *"); WriteLn; WriteString ("* specifically all the order combinations of the characters chosen. *"); WriteLn; WriteString ("* It is important to note that the numbers of possible combinations *"); WriteLn; WriteString ("* increases expedientially and consequently the time needed to find *"); WriteLn; WriteString ("* all the combinations. The number of characters is limited to 80 *"); WriteLn; WriteString ("* characters however any number of characters over 12 would take an *"); WriteLn; WriteString ("* enormous amount of time. *"); WriteLn; WriteString ("************************************************************************"); WriteLn; END Header; BEGIN (* Let the main program begin :)*) Header; REPEAT (* Repeats for rerun of program functions*) REPEAT (* Repeats if the user wants to change their string value*) WriteLn; WriteString ("Enter the word or line you wish to find anagrams of: "); ReadString (Input); (* Get the Users string that they want anagrams for*) SkipLine; (* Clear Buffer*) (*Cacluates the length of the string, used in anagram procedure and is display for user*) StringLengthCon := Length(Input); WriteString ("Length of the string is"); WriteCard (StringLengthCon, 0); WriteString (" characters and the number of possible"); WriteLn; WriteString ("combinations for these characters is"); (* Uses QuickCombNumber Procedure to calculated and display the number of possible combinations*) WriteCard (QuickCombNumber(StringLengthCon), 0); WriteChar("."); WriteLn; (* Promps user to make sure they want to run their string *) WriteString ("Do you wish to continue (Y/N)? "); ReadChar(Choice1); SkipLine; UNTIL ((Choice1 = "Y") OR (Choice1 = "y"));(*If all is good run it, if not loop back*) WriteLn; (* This is the anagram procedure's call, note that the position value shoud be set to 0 or of 'NULL' value*) Anagrams(Input, 0, StringLengthCon); (* Prompts user if they want to run the programs procedures again*) WriteString ("Do you wish to run again (Y/N)? "); ReadChar(Choice2); SkipLine; UNTIL ((Choice2 = "N") OR (Choice2 = "n")); (* If N then quit, else loop and do again*) END AnagramGen. (* Sample Runs: ************************************************************************ *** Nicholas Erho *** CMPT 141 ***** ID: 200613 *** October 13, 2004 *** ************************************************************************ * Anagram Finder * ************************************************************************ * This program is desgined to find all the anagrams or more * * specifically all the order combinations of the characters chosen. * * It is important to note that the numbers of possible combinations * * increases expedientially and consequently the time needed to find * * all the combinations. The number of characters is limited to 80 * * characters however any number of characters over 12 would take an * * enormous amount of time. * ************************************************************************ Enter the word or line you wish to find anagrams of: hello Length of the string is 5 characters and the number of possible combinations for these characters is 120. Do you wish to continue (Y/N)? y 1 : HELLO 2 : HELOL 3 : HELLO 4 : HELOL 5 : HEOLL 6 : HEOLL 7 : HLELO 8 : HLEOL 9 : HLLEO 10 : HLLOE 11 : HLOLE 12 : HLOEL 13 : HLLEO 14 : HLLOE 15 : HLELO 16 : HLEOL 17 : HLOEL 18 : HLOLE 19 : HOLLE 20 : HOLEL 21 : HOLLE 22 : HOLEL 23 : HOELL 24 : HOELL 25 : EHLLO 26 : EHLOL 27 : EHLLO 28 : EHLOL 29 : EHOLL 30 : EHOLL 31 : ELHLO 32 : ELHOL 33 : ELLHO 34 : ELLOH 35 : ELOLH 36 : ELOHL 37 : ELLHO 38 : ELLOH 39 : ELHLO 40 : ELHOL 41 : ELOHL 42 : ELOLH 43 : EOLLH 44 : EOLHL 45 : EOLLH 46 : EOLHL 47 : EOHLL 48 : EOHLL 49 : LEHLO 50 : LEHOL 51 : LELHO 52 : LELOH 53 : LEOLH 54 : LEOHL 55 : LHELO 56 : LHEOL 57 : LHLEO 58 : LHLOE 59 : LHOLE 60 : LHOEL 61 : LLHEO 62 : LLHOE 63 : LLEHO 64 : LLEOH 65 : LLOEH 66 : LLOHE 67 : LOHLE 68 : LOHEL 69 : LOLHE 70 : LOLEH 71 : LOELH 72 : LOEHL 73 : LELHO 74 : LELOH 75 : LEHLO 76 : LEHOL 77 : LEOHL 78 : LEOLH 79 : LLEHO 80 : LLEOH 81 : LLHEO 82 : LLHOE 83 : LLOHE 84 : LLOEH 85 : LHLEO 86 : LHLOE 87 : LHELO 88 : LHEOL 89 : LHOEL 90 : LHOLE 91 : LOLHE 92 : LOLEH 93 : LOHLE 94 : LOHEL 95 : LOEHL 96 : LOELH 97 : OELLH 98 : OELHL 99 : OELLH 100 : OELHL 101 : OEHLL 102 : OEHLL 103 : OLELH 104 : OLEHL 105 : OLLEH 106 : OLLHE 107 : OLHLE 108 : OLHEL 109 : OLLEH 110 : OLLHE 111 : OLELH 112 : OLEHL 113 : OLHEL 114 : OLHLE 115 : OHLLE 116 : OHLEL 117 : OHLLE 118 : OHLEL 119 : OHELL 120 : OHELL Do you wish to run again (Y/N)? n *)