ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
...
*** glibc detected *** /home/ai/iword/wordsolve.0.0.1/wordsolve: corrupted double-linked list: 0x08325e18 ***
^C
Program received signal SIGINT, Interrupt.
[Switching to Thread -1208325936 (LWP 5789)]
0x00110416 in __kernel_vsyscall ()
(gdb) bt
#0 0x00110416 in __kernel_vsyscall ()
#1 0x00b4c953 in __lll_lock_wait_private () from /lib/libc.so.6
#2 0x00ad9e48 in _L_lock_14708 () from /lib/libc.so.6
#3 0x00ad90e4 in __libc_free (mem=0x81a1f18) at malloc.c:3624
#4 0x00a5eabf in _dl_scope_free (old=0x81a1f18) at dl-open.c:175
#5 0x00a5a19d in _dl_map_object_deps (map=0x81a1c60, preloads=0x0,
npreloads=<value optimized out>, trace_mode=0, open_mode=-2147483648)
at dl-deps.c:668
#6 0x00a5eecd in dl_open_worker (a=0xbf9bde5c) at dl-open.c:330
#7 0x00a5b1b6 in _dl_catch_error (objname=0xbf9bde84, errstring=0xbf9bde80,
mallocedp=0xbf9bde8b, operate=0xa5ed30 <dl_open_worker>, args=0xbf9bde5c)
at dl-error.c:178
#8 0x00a5e852 in _dl_open (file=0xb9398d "libgcc_s.so.1",
mode=<value optimized out>, caller_dlopen=0x0, nsid=-2, argc=1,
argv=0xbf9bfef4, env=0xbf9bfefc) at dl-open.c:596
#9 0x00b765d2 in do_dlopen (ptr=0xbf9bdfb4) at dl-libc.c:86
#10 0x00a5b1b6 in _dl_catch_error (objname=0xbf9bdfc4, errstring=0xbf9bdfc0,
mallocedp=0xbf9bdfcb, operate=0xb76570 <do_dlopen>, args=0xbf9bdfb4)
at dl-error.c:178
#11 0x00b76785 in __libc_dlopen_mode (name=0xb9398d "libgcc_s.so.1",
mode=-2147483647) at dl-libc.c:47
#12 0x00b52e89 in init () at ../sysdeps/i386/backtrace.c:43
#13 0x00c039e0 in pthread_once () from /lib/libpthread.so.0
#14 0x00b53065 in __backtrace (array=0xbf9be594, size=64)
at ../sysdeps/i386/backtrace.c:116
#15 0x00acda01 in __libc_message (do_abort=2,
fmt=0xb96864 "*** glibc detected *** %s: %s: 0x%s ***\n")
at ../sysdeps/unix/sysv/linux/libc_fatal.c:150
#16 0x00ad3e1b in malloc_consolidate (av=0xbc2120) at malloc.c:5891
#17 0x00ad6152 in _int_malloc (av=0xbc2120, bytes=11) at malloc.c:4509
#18 0x00ad789a in __libc_calloc (n=11, elem_size=1) at malloc.c:3892
#19 0x0804a7c4 in do_anagram (search=0x81dcc68 "hello") at main.c:401
#20 0x0804ad2f in do_search (type=0x804b66b "anagram") at main.c:550
#21 0x0804ad5b in callback (widget=0x81b6218, data=0x804b66b) at main.c:563
#22 0x00d89409 in IA__g_cclosure_marshal_VOID__VOID (closure=0x81e1428,
return_value=0x0, n_param_values=1, param_values=0xbf9bef7c,
invocation_hint=0xbf9bee8c, marshal_data=0x804ad4a) at gmarshal.c:77
#23 0x00d7bf83 in IA__g_closure_invoke (closure=0x81e1428, return_value=0x0,
n_param_values=1, param_values=0xbf9bef7c, invocation_hint=0xbf9bee8c)
at gclosure.c:490
#24 0x00d8c48d in signal_emit_unlocked_R (node=0x81e2308, detail=0,
instance=0x81b6218, emission_return=0x0, instance_and_params=0xbf9bef7c)
at gsignal.c:2440
#25 0x00d8d997 in IA__g_signal_emit_valist (instance=0x81b6218, signal_id=129,
detail=0, var_args=0xbf9bf1bc "t&�") at gsignal.c:2199
#26 0x00d8db59 in IA__g_signal_emit (instance=0x81b6218, signal_id=129,
detail=0) at gsignal.c:2243
#27 0x00533cc9 in IA__gtk_button_clicked (button=0x81b6218) at gtkbutton.c:889
#28 0x00535616 in gtk_real_button_released (button=0x81b6218)
at gtkbutton.c:1484
#29 0x00d89409 in IA__g_cclosure_marshal_VOID__VOID (closure=0x81e2260,
return_value=0x0, n_param_values=1, param_values=0xbf9bf44c,
invocation_hint=0xbf9bf35c, marshal_data=0x5355d2) at gmarshal.c:77
#30 0x00d7a779 in g_type_class_meta_marshal (closure=0x81e2260,
return_value=0x0, n_param_values=1, param_values=0xbf9bf44c,
invocation_hint=0xbf9bf35c, marshal_data=0x1a4) at gclosure.c:567
#31 0x00d7bf83 in IA__g_closure_invoke (closure=0x81e2260, return_value=0x0,
n_param_values=1, param_values=0xbf9bf44c, invocation_hint=0xbf9bf35c)
at gclosure.c:490
#32 0x00d8c91a in signal_emit_unlocked_R (node=0x81e2298, detail=0,
instance=0x81b6218, emission_return=0x0, instance_and_params=0xbf9bf44c)
at gsignal.c:2370
#33 0x00d8d997 in IA__g_signal_emit_valist (instance=0x81b6218, signal_id=128,
detail=0, var_args=0xbf9bf68c "\221\205�") at gsignal.c:2199
#34 0x00d8db59 in IA__g_signal_emit (instance=0x81b6218, signal_id=128,
detail=0) at gsignal.c:2243
#35 0x00533c22 in IA__gtk_button_released (button=0x81b6218) at gtkbutton.c:881
#36 0x00535368 in gtk_button_button_release (widget=0x81b6218, event=0x81b24a8)
at gtkbutton.c:1377
#37 0x00653434 in _gtk_marshal_BOOLEAN__BOXED (closure=0x81b9998,
return_value=0xbf9bf880, n_param_values=2, param_values=0xbf9bf95c,
invocation_hint=0xbf9bf86c, marshal_data=0x535329) at gtkmarshalers.c:84
#38 0x00d7a779 in g_type_class_meta_marshal (closure=0x81b9998,
return_value=0xbf9bf880, n_param_values=2, param_values=0xbf9bf95c,
invocation_hint=0xbf9bf86c, marshal_data=0xb4) at gclosure.c:567
#39 0x00d7bf83 in IA__g_closure_invoke (closure=0x81b9998,
return_value=0xbf9bf880, n_param_values=2, param_values=0xbf9bf95c,
invocation_hint=0xbf9bf86c) at gclosure.c:490
#40 0x00d8cad3 in signal_emit_unlocked_R (node=0x81b9a80, detail=0,
instance=0x81b6218, emission_return=0xbf9bfb1c,
instance_and_params=0xbf9bf95c) at gsignal.c:2478
#41 0x00d8d75f in IA__g_signal_emit_valist (instance=0x81b6218, signal_id=30,
detail=0, var_args=<value optimized out>) at gsignal.c:2209
#42 0x00d8db59 in IA__g_signal_emit (instance=0x81b6218, signal_id=30,
detail=0) at gsignal.c:2243
#43 0x007df494 in gtk_widget_event_internal (widget=0x81b6218, event=0x81b24a8)
at gtkwidget.c:4678
#44 0x007def98 in IA__gtk_widget_event (widget=0x81b6218, event=0x81b24a8)
at gtkwidget.c:4478
#45 0x006517cb in IA__gtk_propagate_event (widget=0x81b6218, event=0x81b24a8)
at gtkmain.c:2336
#46 0x0065010a in IA__gtk_main_do_event (event=0x81b24a8) at gtkmain.c:1556
#47 0x003a760a in gdk_event_dispatch (source=0x81b5aa8, callback=0,
user_data=0x0) at gdkevents-x11.c:2351
#48 0x0013e1ac in IA__g_main_context_dispatch (context=0x81b5af0)
at gmain.c:2061
#49 0x001415ef in g_main_context_iterate (context=0x81b5af0, block=1,
dispatch=1, self=0x819f990) at gmain.c:2694
#50 0x00141999 in IA__g_main_loop_run (loop=0x8321878) at gmain.c:2898
#51 0x0064f7ee in IA__gtk_main () at gtkmain.c:1163
#52 0x0804b3d7 in main (argc=Cannot access memory at address 0x80
) at main.c:671
(gdb) quit
...
I can invoke the problem on the second run of an 'anagram', usually the word anagram is used. This obviously leads to thinking it's the deletion of my list from the first usage of the function, but in stand alone tests the same problem does not present (hence the long post).
To start with, a few comments about the code you displayed:
1) Rather than writing your own linked list code, check out the standard template library. Unless this is a learning exercise, there's no reason to reinvent the wheel.
2) Your "factorial" function can, fairly rapidly, cause computational inaccuracies.
3) Formulas exist for combinatorial sums, so actually computing the sum seems somewhat perverse.
4) Using two structures when one would suffice is, um, less than optimal.
5) Locating "linked_list[pos]" by counting from 0 when you can insert a list element anywhere in the list means that ll[pos] may not be ll[pos] the next time you look. So the point in using pos as a list index is lost on me.
About your error message: The message seems to have been generated by the gtk, not your code, so it seems likely that you've got a pointer wrong in your linked list code that has let you write into your executable space. It probably happens the second time the code is traversed because the code has been changed (overwritten) by your first run.
Last edited by PTrenholme; 09-11-2008 at 11:22 AM.
1) Isn't the STL actually C++, otherwise point me in the right direction.
2) Not my field at all, new subject.
3) Same as 2.
4) Only adds a single pointer and count (int) to mix, but not really.
5) Once managed, then quick multipass can be achieved.
*** this list wasn't written for this project...
I'll have a revision of the gtk code and see if anythings amiss. I did wonder about using malloc within the list init function earlier.
The stl is, as you note, C++. But it's all source code, and using the code as a template for C code is fairly straight forward.
From your code, it looks like you're trying to find all the "dictionary words" in all possible permutations of the letters of some input string. Perhaps you should consider using a "permutation generation" method to get your permutation.
For example, the "Adjacent Mark" method (see S. M. Johnson, Generation of Permutations by Adjacent Transposition in Mathematical Computation17 (1963) 282-285) of generating all the permutations of a set of values by exchanging a pair of adjacent values at each step. Using that algorithm your "word search" space at each step would only need to consider strings that would be altered by the exchange performed.
Oh, if you're interested, here's a quick-and-dirty C code implementation of the algorithm:
PHP Code:
#include <stdlib.h> #include <string.h> #include <stdio.h> #define debug 0 int main() { char test1[]="1234"; char test2[]="anagram"; int flag = 1, ret; while ((ret = comb(test1, flag)) != -1) { printf("%3d - %s\n", ret, test1); flag=0; } printf("\n"); flag=1; while ((ret = comb(test2, flag)) != -1) { printf("%3d - %s\n", ret, test2); flag=0; } exit (0); } /*****************************************/ /* */ /* Find the next permutation of a string */ /* */ /*****************************************/ int comb( // -1 If no more permutations, // length of string if returned string is unchanged, // otherwise index of character exchanged with next one char * string,// String whose characters are being permuted int new) // Flag. 1 if string is a new string to be permuted, 0 otherwise { static int n = 0, i,j,m, * d = 0, * e = 0, * a = 0; char c; int k; // Are we starting a new string? if (new) { n = strlen(string); if (n < 2) { // Rase error: Called with fewer than two characters in string return -1; } m = n - 1; d = malloc(n * sizeof(int)); e = malloc(n * sizeof(int)); a = malloc(n * sizeof(int)); if (!d || !e || !a ) { // Raise error: Out of memory return -1; } for (i = 0; i < n; ++i) { d[i]=0; e[i]=1; a[i]=i+1; } j = m; return n; } // If here, not initalizing. Find the next permutation, if any step2: a[j] = a[j] - e[j]; if ((a[j] == j + 1) || (a[j]== 0)) { e[j]=-e[j]; d[j]=1 - d[j]; j = j - 1; // Are we done? if (j == 0) { free(d); free(e); free(a); return -1; } goto step2; } k = a[j]; for (i = j + 1; i < n; ++i) { k += d[i]; } c = string[k]; string[k] = string[k - 1]; string[k - 1] = c; return k - 1; }
Thanks, i'll have a go through tomorrow, but I assume it's just the first part of the combinations (not all sizes).
Oh, the reason why I calculated the number of combinations was so I could pre-declare the array.
Being American do you know of 'Countdown' (A daily quiz show here in UK, with the ever so lovely Carol Vordaman)?
Here's a very weird first episode.
But i've not seen this one.
P.S. I think one of my first python versions worked by a similar method to the one you show. My final python one could take upto 50 seconds to work through though (on 9 letters).
I suspect that you want all the (distinct) partitions of the permutations, unless, of course, you're searching for phrases rather than words. The point, if you're searching for words, is that you can't pre-allocate space for the words unless you don't care that many entries might be duplicates.
The solution, I believe, is to use a binary (perhaps hashed) tree to store the "words" and throw out any duplicates. (Or count them if you're interested.)
The point in the adjacent letter switch method is that you only need to look for partitions which contain the switched letters when you're storing the "words."
If I get time, perhaps I'll see if I can put together a package to build the "word" list.
By the way, the "raw" number of partitions of an n-letter string is 2**(n-1), not n!.
Well, no, I don't actually watch much video programming except a little "American Football" in the Fall, so I've never seen "Countdown" nor, in fact, ever heard about it.
To return to you problem:
1) I suspect that you're interested in the partitions of each permutation, not the combinations of letters. The point being that the number of partitions of a n-character string is 2^(n-1), and n! is the number of permutations on things, so the "raw" number of "words" you can generate is (n!)(2^(n-1)). Thus the number of combinations is, perhaps, not too relevant to the problem.
2) In fact, unless you're looking for phrases rather than words in your string, you're probably more interested in the distinct words in the partitions of the permutations on the letters in the input work. That was the point in using the "adjacent letter" permutation method: you only need to look at partrtion containing the "switched" positions for new "words," and then only if the stitched letters are different from each other.
To expand on point 2: If my understanding of your objective is correct, than I believe that you best strategy would be to store the generated "words" in a hashed binary tree, using the first letter as your hash key, and a binary tree under that hash as your (dynamic) storage. So you initial allocation would be an array of binary tree bases, one for each (distinct) letter in you input string. Than store each (distinct) partition under it's hash, either ignoring or counting any duplicated strings.
If I have time, I'll see if I can throw something together.
P.S.: The "ugly" goto in the q&d code above can be eliminated by a while (1) {if ... else break construct. As I said, it was "quic and dirty."
If I was allowed a dog, I'd buy 'it' one of these. [good site]
I'm not sure if i'll read 'Stranger in a Strange Land' by Heinlein, but Case likes the fact about the word 'cyberspace' here, and I learnt a new word, 'neologism'.
The maths is mainly reworked from quite a basic statistics book, developing from what I prised from the python examples, so those short cuts sound good (tomorrow i'll test).
The binary tree concept works by solving the thought of reiterating the list to remove duplicates, which saves the time which wouldn't really be saved (on a large search), (omg i'm lazy at times).
If you're still interested, here's a "all words made from letters in a input stream" solution which relies on Linux tools rather than lists.
First, here's the output (and command line) for "anagram:"
Code:
$ echo anagram | ./comb |sort -u|hunspell -G
a
agar
am
an
anagram
g
gar
gm
gr
gram
m
ma
mag
man
mar
mg
mgr
n
nag
r
rag
ram
ran
rang
rm
and here's the source code:
PHP Code:
/* Find the next permutation of a string */ #include <stdlib.h> #include <string.h> #include <stdio.h> #define debug 0 extern FILE * stdin; extern FILE * stdout; extern FILE * stderr; /**********************************************/ /* "/ /* Partition a string into all its substrings */ /* */ /**********************************************/ void partition( // No reurn value const char * const string, // String to be partitioned FILE * out) // File where each partition is to be written { long int npart; // Number of partitions long int bits; // Binary value holder int n; // Length of input strng register int pos; // Character to be next printed register int k; // Inner loop index long int i; // Current partition number n = strlen(string); npart = ((long int) 1) << (n - 1); for (i = npart - 1; i >= 0; --i) { bits = i; pos=0; while (bits) { fprintf(out,"%c",string[pos++]); if (bits & 1) fprintf(out,"\n"); bits = bits / 2; } if (pos < n) { for (;pos<n;++pos) fprintf(out,"%c",string[pos]); fprintf(out,"\n"); } } }
int comb( // -1 If no more permutations, // length of string if returned string is unchanged, // otherwise index of character exchanged with next one char * string,// String whose characters are being permuted int *new) // Flag. 1 if string is a new string to be permuted, 0 otherwise { static int n = 0, i,j, * d = 0, * e = 0, * a = 0; char c; int k; // Are we starting a new string? if (*new) { n = strlen(string); // Remove any terminating new line character if (string[n-1]=='\n') string[--n]=0; // Do we have anything left? if (n < 2) { fprintf(stderr,"\"%s\" is too short to permute.\n", string); return -1; } d = malloc(n * sizeof(int)); e = malloc(n * sizeof(int)); a = malloc(n * sizeof(int)); if (!d || !e || !a ) { fprintf(stderr,"comb: Insuffent dynamic memory.\n"); if (d) free(d); if (e) free(e); if (a) free(a); return -1; } // Initalize the tracking arrays for (i = 0; i < n; ++i) { d[i]=0; e[i]=1; a[i]=i+1; } // Start the exchage with the last character j = n; // Set the 'new string" flag off *new=0; return n; } // If here, not initalizing. Find the next permutation, if any while (1) { a[j] = a[j] - e[j]; if ((a[j] == j + 1) || (a[j]== 0)) { e[j]=-e[j]; d[j]=1 - d[j]; j = j - 1; // Are we done? if (j < 0) { free(d); free(e); free(a); return -1; } } else break; } k = a[j]; for (i = j + 1; i < n; ++i) { k += d[i]; } c = string[k]; string[k] = string[k - 1]; string[k - 1] = c; return k - 1; }
int main(int argc, char **argv) { FILE * in; // Input file pointer FILE * out; // Output file pointer char word[256]; // Current word holder int i; // Temporary integers (loop indices, etc.) in = (argc > 1) ? fopen(argv[1],"r") : stdin; if (! in) { if (argc > 1) fprintf(stderr, "Could not open %s for input.\n", argv[1]); else fprintf(stderr, "Could not open stdin for input.\n"); exit (1); } out = (argc > 2) ? fopen(argv[2],"w") : stdout; if (! out) { if (argc > 2) fprintf(stderr, "Could not open %s for output.\n", argv[2]); else fprintf(stderr, "Could not open stdout for output.\n"); exit (1); } while (fgets(word, 256, in)) { // Write all permutations of "word' to stdout i = 1; while (comb(word,&i)>=0) { partition(word, stdout); } } exit (0); }
Yes i'm still interested, work caught up with me on Sunday, so i'll probably not have the time I want to dedicate to this until the weekend. But 'hunspell' is a new one on me, a quick perusal of it's man page looks interesting, thanks for the heads up!
O.K., I found your problem interesting, so here's another take that works a little faster. Instead of linked lists, I used SQLite to sort and store the data.
I tried my last code on this string and aborted after an hour or so. This code finished in about 10 minutes.
First, here's the output:
Code:
$ echo averylongstring | ./comb2 | hunspell -G
an
as
at
av
ave
aver
avers
avert
avg
ay
ea
en
er
erg
err
es
gave
gin
gist
go
gong
gongs
gr
grin
gs
gt
in
ion
is
it
iv
la
lav
lave
lay
lg
lion
lo
log
loin
long
longs
lorn
lot
ls
lyre
naive
naiver
nave
no
non
nylon
oi
on
or
over
rat
rave
raver
re
rev
rig
ring
rs
rt
sag
save
saver
sit
so
son
song
st
stir
string
ta
ti
tn
to
ton
tong
tongs
tr
trig
try
ts
veg
very
vet
vi
vie
voe
vs
ya
ye
yer
yo
yr
And here's the source code. Note that I chose to use an "ephemeral" data base, but you could choose to save the information is a data base file and use it in other programs if you wished.
PHP Code:
#include <stdlib.h> #include <string.h> #include <stdio.h> #include <sqlite3.h> #define debug 0 extern FILE * stdin; extern FILE * stdout; extern FILE * stderr; /**********************************************/ /* */ /* SQLite error report helper function */ /* */ /**********************************************/ int check_code( // Return 0 is OK, 1 otherwise sqlite3 * db, // Data base information pointer sqlite3_stmt *stmt, // Statement being checked const int rc, // Value to check const char * text, // Text to print if check fails const int target) // SQLite expected return code { if (rc != target) { fprintf(stderr, "%s: %s\n", text, sqlite3_errmsg(db)); if (stmt) sqlite3_finalize(stmt); return 1; } return 0; } /**********************************************/ /* */ /* Partition a string into all its substrings */ /* */ /**********************************************/ int partition( // Return 0 on success, 1 otherwise const char * const string, // String to be partitioned sqlite3 * db) // Pointer to the SQLite data base to use for storaage { long int npart; // Number of partitions long int bits; // Binary value holder int n; // Length of input string register int pos; // Character to be next printed register int k; // Inner loop index long int i, j; // Current partition number char * str; // Word holder sqlite3_stmt *stmt; // Insert statement holder char * errmsg; int rc; // SQLite return code holder char insert[256];
str = (char *) malloc(n*sizeof(char)); if (!str) { fprintf(stderr,"partition: Could not allocate %d characters for \"str.\"\n", n); return 1; }
// Find the (next) partition and insert it into the data base if it's longer than 1 character j = 0; for (i = npart - 1; i >= 0; --i) { bits = i; pos=0; k = 0; while (bits) { str[k++] = string[pos++]; if (bits & 1) { str[k] = (char) 0; // Add the word to the data base if it's long enough if (k > 1) { sqlite3_snprintf(255, insert, "INSERT INTO WORDS (WORD) VALUES(%Q)", str); rc = sqlite3_exec(db, insert, NULL, NULL, &errmsg); if (check_code(db, stmt, rc, "partition: Problem inserting WORD", SQLITE_OK)) { sqlite3_free(errmsg); sqlite3_close(db); exit (1); } } // And compute the next word . . . ++j; k = 0; } bits = bits / 2; } // Finished with the current value of j. Process any remaining characters. while (pos < n) str[k++] = string[pos++]; str[k] = (char) 0; pos = 0; // Add the last string if it's long enough if (k > 1) { sqlite3_snprintf(255, insert, "INSERT INTO WORDS (WORD) VALUES(%Q)", str); rc = sqlite3_exec(db, insert, NULL, NULL, &errmsg); if (check_code(db, stmt, rc, "partition: Problem inserting WORD", SQLITE_OK)) { sqlite3_free(errmsg); sqlite3_close(db); exit (1); } } bits = --i; k = 0; } return 0; }
int comb( // -1 If no more permutations, // length of string if returned string is unchanged, // otherwise index of character exchanged with next one char * string,// String whose characters are being permuted int *new) // Flag. 1 if string is a new string to be permuted, 0 otherwise { static int n = 0, i,j, * d = 0, * e = 0, * a = 0; char c; int k; // Are we starting a new string? if (*new) { n = strlen(string); // Remove any terminating new line character if (string[n-1]=='\n') string[--n]=0; // Do we have anything left? if (n < 2) { fprintf(stderr,"\"%s\" is too short to permute.\n", string); return -1; } d = malloc(n * sizeof(int)); e = malloc(n * sizeof(int)); a = malloc(n * sizeof(int)); if (!d || !e || !a ) { fprintf(stderr,"comb: Insufficient dynamic memory.\n"); if (d) free(d); if (e) free(e); if (a) free(a); return -1; } // Initialize the tracking arrays for (i = 0; i < n; ++i) { d[i]=0; e[i]=1; a[i]=i+1; } // Start the exchange with the last character j = n - 1; // Set the 'new string" flag off *new=0; return n; } // If here, not initializing. Find the next permutation, if any while (1) { a[j] = a[j] - e[j]; if ((a[j] == j + 1) || (a[j]== 0)) { e[j]=-e[j]; d[j]=1 - d[j]; j = j - 1; // Are we done? if (j == 0) { free(d); free(e); free(a); return -1; } } else break; } k = a[j]; for (i = j + 1; i < n; ++i) { k += d[i]; } c = string[k]; string[k] = string[k - 1]; string[k - 1] = c; return k - 1; }
int main(int argc, char **argv) { char word[256]; // Current word holder char msg[256]; // Potential error message holder int i; register int j,k,l; // Temporary integers (loop index, etc.) // SQLite stuff sqlite3 *db; sqlite3_stmt *stmt = 0; int rc; char create[]="CREATE TABLE WORDS (WORD VARCHAR(255) PRIMARY KEY ON CONFLICT IGNORE)"; char select[]="SELECT WORD FROM WORDS ORDER BY WORD"; char *errmsg = (char *) NULL; // End SQLite stuff
while (fgets(word, 256, stdin)) { // Create a temporary data base to hold the strings found rc = sqlite3_open_v2(NULL, &db, 0, errmsg); sprintf(msg, "%s: Could not open an ephemeral SQLite data base", argv[0]); if (check_code(db, stmt, rc, msg, SQLITE_OK)) { close(db); exit(1); } // Create the table to store the "words" rc = sqlite3_exec(db, create, NULL, NULL, &errmsg); sprintf(msg, "%s: Could not create table WORDS", argv[0]); if (check_code(db, stmt, rc, msg, SQLITE_OK)) { sqlite3_close(db); exit(1); } // Insert all permutations of "word' into the temporary data base i = 1; while (comb(word, &i) >= 0) { if (partition(word, db)) { // If we get here we had a data base error. Abort. sqlite3_close(db); exit (1); } } // Write the "words" stored in the data base to the output file rc = sqlite3_prepare_v2(db, select, -1, &stmt, 0); if (rc != SQLITE_OK) { fprintf(stderr,"%s: Error preparing %s: %s\n", argv[0], select, sqlite3_errmsg(db)); sqlite3_finalize(stmt); exit(1); } while ((rc = sqlite3_step(stmt)) == SQLITE_ROW) { strncpy(word, (char *) sqlite3_column_text(stmt, 0), 255); fprintf(stdout,"%s\n", word); } sprintf(msg, "%s: Error retrieving data from WORDS", argv[0]); check_code( db, stmt, rc, msg, SQLITE_DONE); sqlite3_finalize(stmt); sqlite3_close(db); } exit ((rc==SQLITE_DONE) ? 0 : 1); }
As a further improvement, here's a version that eliminates processing any partition where identical character are being exchanged, and eliminates any duplicates from the strings to be partitioned. Oh, a couple of other things:
1) Whilst writing this code, I inadvertently attempted to free memory which had not,in fact, been allocated. That produced the "double linked list" error message about which you originally asked. So I suspect that your code was somehow trying to free memory you'd not actually allocated.
2) The funny code in main is there because the compiler complained when I used process_sql in the sqlite_exec call. I don't understand why, and, in fact, when I finish this note I'm going to start a thread to see what other people think might be the explanation.
So, here's the revised code. The changes are mostly in main and the recursive call at the end of comb to skip swapping identical characters.
PHP Code:
/* Find the next permutation of a string */ #include <stdlib.h> #include <string.h> #include <stdio.h> #include <sqlite3.h> #define debug 0 extern FILE * stdin; extern FILE * stdout; extern FILE * stderr; /**********************************************/ /* */ /* SQLite error report helper function */ /* */ /**********************************************/ int check_code( // Return 0 is OK, 1 otherwise sqlite3 * db, // Data base information pointer sqlite3_stmt *stmt, // Statement being checked const int rc, // Value to check const char * text, // Text to print if check fails const int target) // SQLite expected return code { if (rc != target) { fprintf(stderr, "%s: %s\n", text, sqlite3_errmsg(db)); if (stmt) sqlite3_finalize(stmt); return 1; } return 0; } /**********************************************/ /* */ /* Partition a string into all its substrings */ /* */ /**********************************************/ int partition( // Return 0 on success, 1 otherwise const char * const string, // String to be partitioned sqlite3 * db) // Pointer to the SQLite data base to use for storage { long int npart; // Number of partitions long int bits; // Binary value holder int n; // Length of input string register int pos; // Character to be next printed register int k; // Inner loop index long int i, j; // Current partition number char * str; // Word holder sqlite3_stmt *stmt; // Insert statement holder char * errmsg; int rc; // SQLite return code holder char insert[256];
str = (char *) malloc(n*sizeof(char)); if (!str) { fprintf(stderr,"partition: Could not allocate %d characters for \"str.\"\n", n); return 1; }
// Find the (next) partition and insert it into the data base if it's longer than 1 character j = 0; for (i = npart - 1; i >= 0; --i) { bits = i; pos=0; k = 0; while (bits) { str[k++] = string[pos++]; if (bits & 1) { str[k] = (char) 0; // Add the word to the data base if it's long enough if (k > 1) { sqlite3_snprintf(255, insert, "INSERT INTO WORDS (WORD) VALUES(%Q)", str); rc = sqlite3_exec(db, insert, NULL, NULL, &errmsg); if (check_code(db, stmt, rc, "partition: Problem inserting WORD", SQLITE_OK)) { sqlite3_free(errmsg); sqlite3_close(db); exit (1); } } // And compute the next word . . . ++j; k = 0; } bits = bits / 2; } // Finished with the current value of j. Process any remaining characters. while (pos < n) str[k++] = string[pos++]; str[k] = (char) 0; pos = 0; // Add the last string if it's long enough if (k > 1) { sqlite3_snprintf(255, insert, "INSERT INTO WORDS (WORD) VALUES(%Q)", str); rc = sqlite3_exec(db, insert, NULL, NULL, &errmsg); if (check_code(db, stmt, rc, "partition: Problem inserting WORD", SQLITE_OK)) { sqlite3_free(errmsg); sqlite3_close(db); exit (1); } } bits = --i; k = 0; } return 0; }
int comb( // -1 If no more permutations, // length of string if returned string is unchanged, // otherwise index of character exchanged with next one char * string,// String whose characters are being permuted int *new) // Flag. 1 if string is a new string to be permuted, 0 otherwise { static int n = 0, i,j, * d = 0, * e = 0, * a = 0; char c; int k; // Are we starting a new string? if (*new) { n = strlen(string); // Remove any terminating new line character if (string[n-1]=='\n') string[--n]=0; // Do we have anything left? if (n < 2) { fprintf(stderr,"\"%s\" is too short to permute.\n", string); return -1; } d = malloc(n * sizeof(int)); e = malloc(n * sizeof(int)); a = malloc(n * sizeof(int)); if (!d || !e || !a ) { fprintf(stderr,"comb: Insufficient dynamic memory.\n"); if (d) free(d); if (e) free(e); if (a) free(a); return -1; } // Initialize the tracking arrays for (i = 0; i < n; ++i) { d[i]=0; e[i]=1; a[i]=i+1; } // Start the exchange with the last character j = n - 1; // Set the 'new string" flag off *new=0; return n; } // If here, not initializing. Find the next permutation, if any while (1) { a[j] = a[j] - e[j]; if ((a[j] == j + 1) || (a[j]== 0)) { e[j]=-e[j]; d[j]=1 - d[j]; j = j - 1; // Are we done? if (j == 0) { free(d); free(e); free(a); return -1; } } else break; } k = a[j]; for (i = j + 1; i < n; ++i) { k += d[i]; } if (string[k-1] != string[k]) { c = string[k]; string[k] = string[k - 1]; string[k - 1] = c; return k - 1; } // Recursive call to deal with exchange of duplicate characters return comb(string, new); }
/******************************************************/ /* */ /* Call-back function used by sqlite3_exec() */ /* */ /******************************************************/ static int process_sql( // Return 0 on success sqlite3 *db, // Data base being processed int argc, // Number of row values returned by query char **argv, // Data values returned char **azColName) // Name of the data columns returned { if (argc < 0) return 1; if (partition(argv[0], db)) { // If we get here we had a data base error. Abort. sqlite3_close(db); exit (1); } // Partition the root word if (partition(argv[0], db)) { // If we get here we had a data base error. Abort. sqlite3_close(db); exit (1); } return 0; }
int main(int argc, char **argv) { char word[256]; // Current word holder char msg[256]; // Potential error message holder int i; register int j,k,l; // Temporary integers (loop index, etc.) // SQLite stuff sqlite3 *db; sqlite3_stmt *stmt = 0; sqlite3_stmt *root = 0; int rc; char create[]= "CREATE TABLE WORDS (WORD TEXT PRIMARY KEY ON CONFLICT IGNORE)"; char select[]= "SELECT WORD FROM WORDS ORDER BY WORD"; char roots[]= "CREATE TABLE ROOTS (ROOT TEXT PRIMARY KEY ON CONFLICT IGNORE)"; char getroot[]="SELECT ROOT FROM ROOTS ORDER BY ROOT"; char command[256]; // Command string holder char *errmsg = (char *) NULL;
// Create a temporary data base to hold the strings found rc = sqlite3_open_v2(NULL, &db, 0, errmsg); sprintf(msg, "%s: Could not open an ephemeral SQLite data base", argv[0]); if (check_code(db, stmt, rc, msg, SQLITE_OK)) { close(db); exit(1); } // Create the table to store the root "words" rc = sqlite3_exec(db, roots, NULL, NULL, &errmsg); sprintf(msg, "%s: Could not create table ROOTS", argv[0]); if (check_code(db, stmt, rc, msg, SQLITE_OK)) { sqlite3_close(db); exit(1); } // Create the table to store the "words" rc = sqlite3_exec(db, create, NULL, NULL, &errmsg); sprintf(msg, "%s: Could not create table WORDS", argv[0]); if (check_code(db, stmt, rc, msg, SQLITE_OK)) { sqlite3_close(db); exit(1); } // End SQLite stuff
// For each input string . ' ' while (fgets(word, 256, stdin)) { // Insert all permutations of "word' into the temporary data base i = 1; while (comb(word, &i) >= 0) { sqlite3_snprintf(255, command, "INSERT INTO WORDS (WORD) VALUES(%Q)", word); rc = sqlite3_exec(db, command, NULL, NULL, &errmsg); sprintf(msg, "%s: Problem inserting WORD (\"%s\")", argv[0], word); if (check_code(db, stmt, rc, msg, SQLITE_OK)) { sqlite3_free(errmsg); sqlite3_close(db); exit (1); } } } // O.K., now all the unique, permuted strings from the input are ready to be partitioned. Do it. // // Note: The processing is done in the call-back routine, "process_sql" // rc = sqlite3_exec(db, select, (sqlite3_callback) process_sql, db, &errmsg); sprintf(msg, "%s: Problem creating WORDS", argv[0]); if (check_code(db, stmt, rc, msg, SQLITE_OK)) { sqlite3_free(errmsg); sqlite3_close(db); exit(1); } // Write the "words" stored in the data base to the output file rc = sqlite3_prepare_v2(db, select, -1, &stmt, 0); if (rc != SQLITE_OK) { fprintf(stderr,"%s: Error preparing %s: %s\n", argv[0], select, sqlite3_errmsg(db)); sqlite3_finalize(stmt); exit(1); } while ((rc = sqlite3_step(stmt)) == SQLITE_ROW) { strncpy(word, (char *) sqlite3_column_text(stmt, 0), 255); fprintf(stdout,"%s\n", word); } sprintf(msg, "%s: Error retrieving data from WORDS", argv[0]); check_code( db, stmt, rc, msg, SQLITE_DONE); sqlite3_finalize(stmt); sqlite3_close(db); exit ((rc==SQLITE_DONE) ? 0 : 1); }
Last edited by PTrenholme; 09-30-2008 at 05:42 PM.
Reason: Changed the sqlite3_exec call in main() to cast the callback to a sqlite3_callback pointer
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.
