So given a string of up to 7 letters, I need to find every permutation of that string (with and without all the letters) and then check if any of those permutations can be found in my dictionary.txt file, and print the ones that match. So basically, if the user inputs "try," the permutations would be try, tr, tyr, ty, t, rty, etc., and then check if any of them match words in the txt file. I tried to do this using strncopy and strcmp, but the program doesn't always correctly deduce that two things are equal, it takes forever to run, and there's a bug where it counts having zero letters as a permutation of the original string.
Here is my code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 100 /* number of words in dictionary.txt */
#define MAX 7 /* max number of letters in given string */
/* function to swap values at two pointers */
void swap(char *x, char *y){
char temp;
temp = *x;
*x = *y;
*y = temp;
}
/* function to find permutations of the string */
void permute(char *letters, int l, int r){
if (l == r){
char *a[SIZE];
FILE *file = fopen("dictionary.txt", "r");
char target[MAX_2];
memset(target, '\0', sizeof(target));
for (int i = 0; i < SIZE; i ){
a[i] = malloc(100000);
fscanf(file, "%s", a[i]);
}
for (int i = 0; i < 10; i ){
for (int j = 0; j < r - 1; j ){
strcpy(target, a[i]);
if (strcmp(target, &letters[i]) == 0){
printf("%s\n", target);
printf("%s\n", letters);
printf("Match\n");
}
/*else if (strcmp(target, &letters[i]) != 0){
printf("%s\n", target);
printf("%s\n", letters);
printf("Not a match\n");
}
*/
}
}
for (int i = 0; i < SIZE; i ){
free (a[i]);
}
fclose(file);
}
else{
for (int i = l; i <= r; i ){
swap((tiles l), (tiles i));
permute(tiles, l 1, r);
swap((tiles l), (tiles i));
}
}
}
int main(){
/* initializing tile input */
char letters[MAX];
printf("Please enter your letters: ");
scanf("%s", letters);
/* finding size of input */
int size = strlen(letters);
/* finds all the permutation of the input */
/* parameters: string; start of the string; end of the string */
permute(letters, 0, size);
return 0;
}
Any help or suggestions to pinpoint what I'm doing wrong would be greatly appreciated.
CodePudding user response：
As hinted in my comment, you can map all permutations of a string to a single code value, just by using the bits of a big enough unsigned integer as a bit set. Thus, the (same length) permutations of e.g. the word "try" all map to the same value.
As far as I understood your problem, you also want to match words, which start out with a substring of the wanted word. For that to work, you need to generated N such codes, if N is the number of letters, a word contains. I.e. For a three letter word, the code for the first letter, the first 2 letters and the code for all 3 letters.
Since reading from a file is probably not the problem, here the code, showcasing the "code based" string matching idea (which should be reasonably fast):
#include <stdio.h>
#include <inttypes.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAX_WORD_LENGTH 7
typedef uint32_t WordCode;
typedef struct WordCodes_tag {
size_t count;
WordCode codes[MAX_WORD_LENGTH];
} WordCodes_t;
bool word_to_code(const char* word,
size_t start,
size_t end,
WordCode* code) {
if ((end - start) > MAX_WORD_LENGTH)
return false;
*code = 0;
for (size_t i = start; i < end; i ) {
char c = word[i];
if ((c >= 'a') && (c <= 'z')) {
char bit = c - 'a';
WordCode mask = 1 << bit;
(*code) |= mask;
} else {
return false;
}
}
return true;
}
bool word_to_codes(const char* word, WordCodes_t* codes) {
if (NULL == codes)
return false;
if (NULL == word)
return false;
codes->count = 0;
size_t nchars = strlen(word);
if (nchars > MAX_WORD_LENGTH)
return false;
for (size_t len = nchars; len >= 1; len--) {
WordCode word_code;
if (word_to_code(word, 0, len, &word_code)) {
codes->codes[codes->count] = word_code;
codes->count ;
} else {
return false;
}
}
return true;
}
void show_word_codes(const WordCodes_t* codes) {
if (NULL == codes) return;
printf("(");
for (size_t i = 0; i < codes->count; i ) {
if (i > 0)
printf(", %d", codes->codes[i]);
else
printf("%d", codes->codes[i]);
}
printf(")\n");
}
bool is_match(const WordCodes_t* a, const WordCodes_t* b) {
if ((NULL == a) || (NULL == b))
return false;
if ((0 == a->count) || (0 == b->count))
return false;
const WordCodes_t *temp = NULL;
if (a->count < b->count) {
temp = a;
a = b;
b = temp;
}
size_t a_offset = a->count - b->count;
for (size_t i = a_offset, j = 0; i < a->count; i , j ) {
if (a->codes[i] == b->codes[j])
return true;
}
return false;
}
int main(int argc, const char* argv[]) {
const char* wanted = "try";
const char* dictionary[] = {
"house", "mouse", "cat", "tree", "try", "yrt", "t"
};
size_t dict_len = sizeof(dictionary) / sizeof(char*);
WordCodes_t wanted_codes;
if (word_to_codes(wanted, &wanted_codes)) {
printf("word codes of the wanted word '%s': ", wanted);
show_word_codes(&wanted_codes);
for (size_t i = 0; i < dict_len; i ) {
WordCodes_t found_codes;
if (word_to_codes(dictionary[i],&found_codes)) {
printf("word codes of dictionary word '%s' (%s): ",
dictionary[i],
is_match(&wanted_codes, &found_codes) ?
"match" : "no match");
show_word_codes(&found_codes);
} else {
printf("word_to_codes(%s) failed!", dictionary[i]);
}
}
} else {
puts("word_to_codes() failed!");
return -1;
}
}
As function is_match() above shows, you need only compare the codes for the respective substring length. Thus, even if you have 2 sets of up to 7 numbers, you need only maximum 7 comparisons.
The output looks like this (which seems to make sense):
./search
word codes of the wanted word 'try': (17432576, 655360, 524288)
word codes of dictionary word 'house' (no match): (1327248, 1327232, 1065088, 16512, 128)
word codes of dictionary word 'mouse' (no match): (1331216, 1331200, 1069056, 20480, 4096)
word codes of dictionary word 'cat' (no match): (524293, 5, 4)
word codes of dictionary word 'tree' (match): (655392, 655376, 655360, 524288)
word codes of dictionary word 'try' (match): (17432576, 655360, 524288)
word codes of dictionary word 'yrt' (match): (17432576, 16908288, 16777216)
word codes of dictionary word 't' (match): (524288)
CodePudding user response：
If you want to match the words in a dictionary against all partial permutations of a search term, you don't have to create all permutations. (The number of permutations n! grows very quickly with the length of the search term, n.)
Instead, it is easier to write a customized search function. You can make use of two strategies here:
A word w is a permutation of the search term s if both words are eaqual if the letters are sorted. For example, "integral" and "triangle" are anagrams of each other, because both sort to "aegilnrt".
You can skip letters in the search term when searching to account for partial anagrams. Because the search term and the word will be sorted, you know which ones to skip: The ones that are lexically "smaller" than the next letter in the word.
So your matching function should sort the words first and then compare the words character by character in such a way that characters from the search term can be skipped.
Here's code that does that:
int char_cmp(const void *pa, const void *pb)
{
const char *a = pa;
const char *b = pb;
return *a - *b;
}
bool partial_anagram(const char *aa, const char *bb)
{
char A[64];
char B[64];
const char *a = strcpy(A, aa);
const char *b = strcpy(B, bb);
qsort(A, strlen(A), 1, char_cmp);
qsort(B, strlen(B), 1, char_cmp);
while (*b) {
while (*a && *a < *b) a ;
if (*a != *b) return false;
a ;
b ;
}
return true;
}
Things to note:
Sorting is done with the function
qsortfrom<stdlib.h>, for which you need a comparator function, in this casechar_cmp.The sorted strings are copies, so that the original strings are not modified. (The code above is unsafe, because it doesn't enforce that the length of the strings is less than 64 characters. Unfortunately, the function
strncpy, which can accept a maximum buffer size, is not safe, either, because it can leave the buffer unterminated. A safe way to copy the strings would besnprintf(A, sizeof(A), "%s", aa), but I've kept thestrcpyfor, er, "simplicity".)The function
partial_anagramtakes unsorted strings and sorts them. That makes for a clean interface, but it is inefficient when you want to test against the same search term repeatedly as in your case. You could change the function, so that it expects already sorted strings. This will reduce the function to just the loop and will place the responsibility of sorting to the caller.If you really have a lot of searches, there is yet more room for optimization. For example, you could insert the sorted dictionary into a trie. Given that you original code read the whole file for each permutation, I guess you're not worried that much about performance.
:)
I've put a 
I use a PATRiCA tree for maximum space-saving; it is especially attractive because a lot of data is implied; one can use a simple array. For the C language especially, I don't have to create copies of everything and manage them. (First I need to create a dynamic array. Then create a trie.)
#include <stdlib.h> /* EXIT malloc free qsort */
#include <stdio.h> /* printf */
#include <string.h> /* memmove memcpy */
#include <assert.h> /* assert */
#include <errno.h> /* errno */
#include <limits.h> /* UINT_MAX */
#include <ctype.h> /* isgraph */
#define MIN_ARRAY(name, type) \
struct name##_array { type *data; size_t size, capacity; }; \
static int name##_array_reserve(struct name##_array *const a, \
const size_t min) { \
size_t c0; \
type *data; \
const size_t max_size = (size_t)-1 / sizeof *a->data; \
if(a->data) { \
if(min <= a->capacity) return 1; \
c0 = a->capacity < 7 ? 7 : a->capacity; \
} else { \
if(!min) return 1; \
c0 = 7; \
} \
if(min > max_size) return errno = ERANGE, 0; \
/* `c_n = a1.625^n`, approximation golden ratio `\phi ~ 1.618`. */ \
while(c0 < min) { \
size_t c1 = c0 (c0 >> 1) (c0 >> 3); \
if(c0 >= c1) { c0 = max_size; break; } /* Unlikely. */ \
c0 = c1; \
} \
if(!(data = realloc(a->data, sizeof *a->data * c0))) \
{ if(!errno) errno = ERANGE; return 0; } \
a->data = data, a->capacity = c0; \
return 1; \
} \
static type *name##_array_buffer(struct name##_array *const a, \
const size_t n) { \
if(a->size > (size_t)-1 - n) { errno = ERANGE; return 0; } \
return name##_array_reserve(a, a->size n) \
&& a->data ? a->data a->size : 0; \
} \
static type *name##_array_append(struct name##_array *const a, \
const size_t n) { \
type *b; \
if(!(b = name##_array_buffer(a, n))) return 0; \
return a->size = n, b; \
} \
static type *name##_array_new(struct name##_array *const a) \
{ return name##_array_append(a, 1); } \
static struct name##_array name##_array(void) \
{ struct name##_array a; a.data = 0, a.capacity = a.size = 0; return a; } \
static void name##_array_(struct name##_array *const a) \
{ if(a) free(a->data), *a = name##_array(); }
MIN_ARRAY(char, char)
struct branch { unsigned skip, left; };
static const size_t skip_max = UINT_MAX, left_max = UINT_MAX;
MIN_ARRAY(branch, struct branch)
MIN_ARRAY(leaf, char *)
/** Trie is a full binary tree in the style of <Morrison, 1968 PATRICiA>.
(_Ie_, for brevity, too much information is contained in this data
structure.) */
struct trie { struct branch_array branches; struct leaf_array leaves; };
static struct trie trie(void) { struct trie t;
t.branches = branch_array(), t.leaves = leaf_array(); return t; }
static void trie_(struct trie *const t) { if(t) branch_array_(&t->branches),
leaf_array_(&t->leaves), *t = trie(); }
/** From string `a`, extract `bit`, either 0 or 1. */
static int is_bit(const char *const a, const size_t bit) {
const size_t byte = bit >> 3;
const unsigned char mask = 128 >> (bit & 7);
return !!(a[byte] & mask);
}
/** @return Whether `a` and `b` are equal up to the minimum of their lengths'. */
static int is_prefix(const char *a, const char *b) {
for( ; ; a , b ) {
if(*a == '\0') return 1;
if(*a != *b) return *b == '\0';
}
}
/** Append a file, `fp`, to `c`, and add a '\0'.
@return Success. A partial read is failure. @throws[fopen, fread, malloc]
@throws[EISEQ] The text file has embedded nulls.
@throws[ERANGE] If the standard library does not follow POSIX. */
static int append_file(struct char_array *c, FILE *const fp) {
const size_t granularity = 4096;
size_t nread;
char *cursor;
int success = 0;
assert(c && fp);
/* Read entire file in chunks. */
do if(!(cursor = char_array_buffer(c, granularity))
|| (nread = fread(cursor, 1, granularity, fp), ferror(fp))
|| !char_array_append(c, nread)) goto catch;
while(nread == granularity);
/* File to `C` string. */
if(!(cursor = char_array_new(c))) goto catch;
*cursor = '\0';
/* Binary files with embedded '\0' are not allowed. */
if(strchr(c->data, '\0') != cursor) { errno = EILSEQ; goto catch; }
{ success = 1; goto finally; }
catch:
if(!errno) errno = EILSEQ; /* Will never be true on POSIX. */
finally:
if(fp) fclose(fp);
return success;
}
/** [low, high). */
struct range { size_t low, high; };
static int init_branches_r(struct trie *const t, size_t bit,
const struct range range) {
struct range r;
size_t skip = 0, left;
struct branch *branch;
assert(t && t->leaves.size);
assert(t->branches.capacity >= t->leaves.size - 1);
assert(range.low <= range.high && range.high <= t->leaves.size);
if(range.low 1 >= range.high) return 1; /* Only one, leaf. */
/* Endpoints of sorted range: skip [_1_111...] or [...000_0_] don't care. */
while(is_bit(t->leaves.data[range.low], bit)
|| !is_bit(t->leaves.data[range.high - 1], bit)) {
if(skip == skip_max) return errno = ERANGE, 0;
bit , skip ;
}
/* Binary search for the rightmost 0 ( 1). */
r = range;
while(r.low < r.high) {
size_t m = r.low (r.high - r.low) / 2;
if(is_bit(t->leaves.data[m], bit)) r.high = m; else r.low = m 1;
}
if((left = r.low - range.low - 1) > left_max) return errno = ERANGE, 0;
/* Should have space for all branches pre-allocated. */
branch = branch_array_new(&t->branches), assert(branch);
branch->left = (unsigned)left;
branch->skip = (unsigned)skip;
bit ;
return (r.low = range.low, r.high = range.low left 1,
init_branches_r(t, bit, r)) && (r.low = r.high, r.high = range.high,
init_branches_r(t, bit, r)) /* && (printf("}\n"), 1) */;
}
/** Orders `a` and `b` by their pointed-to-strings. @implements qsort bsearch */
static int vstrcmp(const void *const a, const void *const b)
{ return strcmp(*(const char *const*)a, *(const char *const*)b); }
/** @param[a] A zero-terminated file containing words. Will be parsed and
modified.
@param[t] An idle tree that is initialized from `a`. Any modification of `a`
invalidates `t`.
@return Whether the tree initialization was entirely successful. */
static int build_trie(struct trie *const t, struct char_array *const a) {
struct range range;
size_t i;
char *cursor, *end, **leaf;
int is_run = 0;
/* Strict for processing ease; this could be made more permissive. */
assert(a && a->size && a->data[a->size - 1] == '\0'
&& t && !t->branches.size && !t->leaves.size);
for(cursor = a->data, end = a->data a->size; cursor < end; cursor ) {
/* Fixme: 7-bit; mælström would be parsed as "m", "lstr", "m". */
if(!isgraph(*cursor)) {
*cursor = '\0', is_run = 0;
} else if(!is_run) {
if(!(leaf = leaf_array_new(&t->leaves))) return 0;
*leaf = cursor, is_run = 1;
}
}
if(!t->leaves.size) return errno = EILSEQ, 0; /* No parseable info. */
/* Sort and de-duplicate (inefficiently.) Want to treat it as an index. */
qsort(t->leaves.data, t->leaves.size, sizeof *t->leaves.data, &vstrcmp);
for(i = 1; i < t->leaves.size; i ) {
if(strcmp(t->leaves.data[i - 1], t->leaves.data[i]) < 0) continue;
fprintf(stderr, "build_index warning: removed duplicate \"%s\".\n",
t->leaves.data[i]);
memmove(t->leaves.data i, t->leaves.data i 1,
sizeof *t->leaves.data * (t->leaves.size - i - 1));
t->leaves.size--, i--;
}
range.low = 0, range.high = t->leaves.size;
if(!branch_array_reserve(&t->branches, t->leaves.size - 1)
|| !init_branches_r(t, 0, range)) return 0;
assert(t->branches.size 1 == t->leaves.size);
return 1;
}
/** @return In `t`, which must be non-empty, given a partial `prefix`, stores
all leaf prefix matches, only given the index, ignoring don't care bits.
@order \O(`prefix.length`) */
static struct range partial_prefix(const struct trie *const t,
const char *const prefix) {
size_t n0 = 0, n1 = t->branches.size, i = 0, left;
struct branch *branch;
size_t byte, key_byte = 0, bit = 0;
struct range range = { 0, 0 };
assert(t && prefix);
assert(n1 1 == t->leaves.size); /* Full binary tree. */
while(n0 < n1) {
branch = t->branches.data n0;
bit = branch->skip;
/* '\0' is not included for partial match. */
for(byte = bit >> 3; key_byte <= byte; key_byte )
if(prefix[key_byte] == '\0') goto finally;
left = branch->left;
if(!is_bit(prefix, bit )) n1 = n0 left;
else n0 = left 1, i = left 1;
}
assert(n0 == n1);
finally:
assert(n0 <= n1 && i - n0 n1 < t->leaves.size);
range.low = i, range.high = i - n0 n1 1;
return range;
}
/* @return Given a `prefix`, what is the range of matched strings in `t`. */
static struct range prefix(const struct trie *const t,
const char *const prefix) {
struct range range;
assert(t && prefix);
if(!t->leaves.size) goto catch;
range = partial_prefix(t, prefix);
if(range.low <= range.high)
if(!is_prefix(prefix, t->leaves.data[range.low])) goto catch;
goto finally;
catch:
range.low = range.high = 0;
finally:
return range;
}
/** Graph: given a branch `b` in `tree` branches, calculate the right child
branches. @order \O(log `size`) */
static unsigned right_count(const struct trie *const tr,
const unsigned b) {
unsigned left, right, total = (unsigned)tr->branches.size, b0 = 0;
assert(tr && b < tr->branches.size);
for( ; ; ) {
right = total - (left = tr->branches.data[b0].left) - 1;
assert(left < total && right < total);
if(b0 >= b) break;
if(b <= b0 left) total = left, b0 ;
else total = right, b0 = left 1;
}
assert(b0 == b);
return right;
}
/** Graph. @return Follows the branches to `b` in `tree` and returns the leaf. */
static unsigned left_leaf(const struct trie *const tr,
const unsigned b) {
unsigned left, right, total = (unsigned)tr->branches.size, i = 0, b0 = 0;
assert(tr && b < tr->branches.size);
for( ; ; ) {
right = total - (left = tr->branches.data[b0].left) - 1;
assert(left < tr->branches.size && right < tr->branches.size);
if(b0 >= b) break;
if(b <= b0 left) total = left, b0 ;
else total = right, b0 = left 1, i = left 1;
}
assert(b0 == b);
return i;
}
static void graph(const struct trie *const tr, const char *const fn) {
unsigned left, right, b, i;
FILE *fp = 0;
assert(tr && fn);
if(!(fp = fopen(fn, "w"))) { perror(fn); return; }
fprintf(fp, "digraph {\n"
"\tgraph [truecolor=true, bgcolor=transparent];\n"
"\tfontface=modern;\n"
"\tnode [shape=none];\n"
"\n");
if(!tr->branches.size) {
assert(!tr->leaves.size);
fprintf(fp, "\tidle;\n");
} else {
assert(tr->branches.size 1 == tr->leaves.size);
fprintf(fp, "\t// branches\n");
for(b = 0; b < tr->branches.size; b ) { /* Branches. */
const struct branch *branch = tr->branches.data b;
left = branch->left, right = right_count(tr, b);
fprintf(fp, "\ttree%pbranch%u [label = \"%u\", shape = circle, "
"style = filled, fillcolor = Grey95];\n"
"\ttree%pbranch%u -> ", (const void *)tr, b, branch->skip,
(const void *)tr, b);
if(left) fprintf(fp, "tree%pbranch%u [arrowhead = rnormal];\n",
(const void *)tr, b 1);
else fprintf(fp,
"tree%pleaf%u [color = Gray85, arrowhead = rnormal];\n",
(const void *)tr, left_leaf(tr, b));
fprintf(fp, "\ttree%pbranch%u -> ", (const void *)tr, b);
if(right) fprintf(fp, "tree%pbranch%u [arrowhead = lnormal];\n",
(const void *)tr, b left 1);
else fprintf(fp,
"tree%pleaf%u [color = Gray85, arrowhead = lnormal];\n",
(const void *)tr, left_leaf(tr, b) left 1);
}
}
fprintf(fp, "\t// leaves\n");
for(i = 0; i < tr->leaves.size; i ) fprintf(fp,
"\ttree%pleaf%u [label = <%s<FONT COLOR=\"Gray85\">⊔</FONT>>];\n",
(const void *)tr, i, tr->leaves.data[i]);
fprintf(fp, "\n"
"\tnode [color = \"Red\"];\n"
"}\n");
fclose(fp);
}
/* Dynamic array. Trie. /\
Actual program. \/ */
/* The input argument histogram. Used in <fn:find_r>. (Simple, but questionable
design choice.) */
static unsigned char hist[128];
static const size_t hist_max = UCHAR_MAX,
hist_size = sizeof hist / sizeof *hist;
static size_t words_found;
/** Branch and bound recursive function. */
static void find_r(const struct trie *const tr, char *const word) {
struct range r;
size_t len, i;
assert(word);
r = prefix(tr, word);
if(r.low >= r.high) return; /* Found nothing, we can bound this branch. */
if(!strcmp(word, tr->leaves.data[r.low])) { /* Found a match. */
printf("%s\n", word), words_found ;
if( r.low == r.high) return;
}
len = strlen(word);
for(i = 0; i < hist_size; i ) {
unsigned char *freq;
if(!*(freq = hist i)) continue;
(*freq)--;
word[len] = (char)i, word[len 1] = '\0';
find_r(tr, word);
(*freq) ;
}
}
int main(int argc, char *argv[]) {
struct char_array dict = char_array();
struct trie tr = trie();
char *word;
size_t i;
int success = EXIT_FAILURE;
assert(CHAR_BIT == 8); /* C89 this value can change, assumes C99 value. */
if(argc != 2) { errno = EILSEQ;
fprintf(stderr, "Needs argument and dictionary input.\n"); goto catch; }
word = argv[1];
/* Load the dictionary from stdin and index it into a trie. */
if(!append_file(&dict, stdin) || !build_trie(&tr, &dict)) goto catch;
fprintf(stderr, "Loaded %lu trie entries.\n",(unsigned long)tr.leaves.size);
graph(&tr, "dictionary.gv");
/* Histogram the argument. */
for(i = 0; word[i] != '\0'; i ) {
unsigned char *freq;
if(word[i] & 0x80) continue; /* UTF-8 is not supported. :[ */
if(*(freq = hist word[i]) == hist_max)
{ errno = ERANGE; goto catch; } /* "aaaaaaaaa..." x 5M? */
(*freq) ;
}
/* Might as well re-use the word now that we're finished with it; it's the
right length. */
*word = '\0', find_r(&tr, word);
/* Global. */
fprintf(stderr, "%lu words found.\n", (unsigned long)words_found);
{ success = EXIT_SUCCESS; goto finally; }
catch:
perror("word");
finally:
trie_(&tr);
char_array_(&dict);
return success;
}