#include <stdio.h>
#include <stdlib.h>
#define MAX_STRING_LENGTH 256
#define NOT_FOUND -1
void RecursivePermute(char str[], char** pList, int length, int k);
void ExchangeCharacters(char str[], int i, int j);
int BinarySearch(char** pList, int n, char TARGET[]);
char** readList(char* fileName, int* wordsCount);
void printList(char** pList, int length);
void freeList(char** pList, int length);
int main(void)
{
char dict_file_name[50];
char** dict_pointer_list;
int dict_words;
FILE* jumb_file;
int jumb_words;
int index;
puts("Enter the file name of your dictionary.");
gets(dict_file_name);
dict_pointer_list = readList(dict_file_name, &dict_words);
jumb_file = fopen("jumble.txt", "r");
fscanf(jumb_file, "%d", &jumb_words);
char cur_jumb_word[30][jumb_words];
// Loop through each word, finding each permutation for that word, and a
// binary search for each permutation. Print out to the screen for each
// permutation that is a valid word.
for (index = 0; index < jumb_words; index++)
{
fscanf(jumb_file, "%s", cur_jumb_word[index]);
printf("\nJumble %d: A permutation of %s that is a valid word is ", index + 1, cur_jumb_word[index]);
RecursivePermute(cur_jumb_word[index], dict_pointer_list, dict_words, 0);
}
// Close the jumble.txt file, and free the memory allocated to dictionary list
// because we are done with them.
fclose(jumb_file);
freeList(dict_pointer_list, dict_words);
puts("\n");
system("PAUSE");
return 0;
}
// Pre-condition: str is a valid C String, pList is a valid pointer
// to an array of pointers, length is amount of words
// in pList, and k is non-negative and less than or equal
// to the length of str.
// Post-condition: All of the permutations of str with the first k
// characters fixed in their original positions are
// found. Namely, if n is the length of str, then
// (n-k)! permutations are found. For each permutation
// a binary search is performed on the dictionary.
void RecursivePermute(char str[], char** pList, int length, int k)
{
int index, j;
if (k == strlen(str))
{
index = BinarySearch(pList, length, str);
if (index == NOT_FOUND);
else
printf("%s. ", pList[index]);
}
// Loop through each possible starting letter for index k,
// the first index for which we have a choice.
for (j=k; j<strlen(str); j++)
{
// Place the character stored in index j in location k.
ExchangeCharacters(str, k, j);
// Find all of the permutations with that character
// just chosen above fixed.
RecursivePermute(str, pList, length, k+1);
// Put the original character that used to be there back
// in its place.
ExchangeCharacters(str, j, k);
}
}
// Pre-condition: str is a valid C String and i and j are valid indexes
// to that string.
// Post-condition: The characters at index i and j will be swapped in
// str.
void ExchangeCharacters(char str[], int i, int j)
{
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
// Pre-condition: pList is a pointer to an array of pointers sorted in ascending
// order of size greater than or equal to n.
// Post-condition: If TARGET is stored in pList in an index in between 0 and n-1,
// then an index in which TARGET is stored is returned.
// Otherwise, -1 is returned.
int BinarySearch(char** pList, int n, char TARGET[])
{
// Set the left and rightmost boundaries in which to search.
int L = 0, Mid, R = n-1;
// Keep on looking so long as there is a search space.
while (L <= R)
{
// Find the element in the middle of the search space.
Mid = (L+R)/2;
// We got a direct hit.
if (strcmp(TARGET, pList[Mid]) == 0)
{
return Mid;
}
// We know that if TARGET is in pList, then it will be located
// to the right of pList[Mid].
else if (strcmp(TARGET, pList[Mid]) > 0)
{
L = Mid + 1;
}
// We know that if TARGET is in pList, then it will be located
// to the left of pList[Mid].
else
{
R = Mid - 1;
}
}
return NOT_FOUND;
}
// Pre-conditions: fileName is the name of a valid file with the proper
// format, and wordsCount is a pointer to an integer that will
// store the number of words read in.
// Post-condition: A pointer to an array of pointers storing all the words in
// filename will be returned.
char** readList(char* fileName, int* wordsCount)
{
char** pList = NULL;
char word[MAX_STRING_LENGTH];
int i, wordLength;
FILE* pFile = fopen(fileName, "r"); // open file.
if (pFile != NULL)
{
// read the 1st line, get to know how many words in the dictionary.
fscanf(pFile, "%d", wordsCount);
/* Here we allocate space a pointer for each word in the list.
Note that the space for the words themselves is NOT allocated here. */
pList = (char **)malloc(*wordsCount * sizeof(char *));
for (i = 0; i < *wordsCount; i++)
{
// read in this word.
fscanf(pFile, "%s", word);
// Allocate one extra spot for the null character.
wordLength = strlen(word) + 1;
// Allocate space for this individual word.
pList[i] = (char *)malloc(wordLength);
// copy the word to the memory block.
strcpy(pList[i], word);
}
fclose(pFile); // close file.
}
return pList;
}
// Pre-condition: pList is a pointer to an array of pointers, each of which
// already stores a string. length is the number of strings
// stored in the structure.
// Post-condition: All of the strings stored in pList will be printed.
void printList(char** pList, int length)
{
int i;
printf("%d\n", length);
// Just loop through each pointer and print the appropriate string.
for (i=0; i<length; i++)
puts(pList[i]);
}
// Pre-condition: pList is a pointer to an array of pointers, each of which
// already stores a string. length is the number of strings
// stored in the structure.
// Post-condition: The memory for the structure pointed to by pList will be
// freed.
void freeList(char** pList, int length)
{
int i;
// Free the memory for each individual word.
for (i=0; i<length; i++)
free(pList[i]);
// Free the pointers to each word.
free(pList);
}
