Hi,
I am doing a little program who calculates the permutation of a set of
vertex.
I use the recursivity for this calcul.
My function who calculate the permutations :
void permutation(set *e, int *current, int nbre)
{
set *p, *copie;
int *tmp;
int i;
if(e != NULL)
{
p = e;
tmp = realloc(current, sizeof *current *(nbre+1));
if(tmp == NULL) exit(-1);
else current = tmp;
while(p != NULL)
{
copie = copie_elt(e); // the function copie_elt let to copy the
set e and to return this copy
current[nbre] = p->st;
delete_elt(&copie,p->st); // this function let to delete an
element of copie. The element who
// is associated with the value p->st
permutation(copie,current,nbre+1); // call of permutation with the
set reducted.
p = p->suivant;
}
}else{
// In current, we have stocked the current permutation,
so we print it
for(i=0; i<nbre; i++)
printf("%d - ",current[i]);
printf("\n");
}
}
I call it in the main with :
/* initialization of the variable e */
permutation(set,current,0);
By executing the program, I have this on my screen (I tried to debug
with GDB) :
(gdb) run
3 - 1 - 2 - 4 -
*** glibc detected *** double free or corruption (fasttop): 0x0804a048
***
Program received signal SIGABRT, Aborted.
0x4004ea27 in raise () from /lib/tls/libc.so.6
(gdb)
So, I tried this function with a char * for the variable current, the
code gives it :
void permutation(set *e, char *current, int nbre)
{
set *p, *copie;
char *tmp;
int i;
if(e != NULL)
{
p = e;
tmp = realloc(current, sizeof *current *(nbre+1));
if(tmp == NULL) exit(-1);
else current = tmp;
while(p != NULL)
{
copie = copie_elt(e); // the function copie_elt let to copy the
set e and to return this copy
current[nbre] = p->st;
delete_elt(&copie,p->st); // this function let to delete an
element of copie. The element who
// is associated with the value p->st
permutation(copie,current,nbre+1); // call of permutation with the
set reducted.
p = p->suivant;
}
}else{
// In current, we have stocked the current permutation,
so we print it
for(i=0; i<nbre; i++)
printf("%d - ",current[i]);
printf("\n");
}
}
I call it in the main with :
permutation(e,current,0);
And there, the program gives the waited answer :
(gdb) run
3 - 1 - 2 - 4 -
3 - 1 - 4 - 2 -
3 - 2 - 1 - 4 -
3 - 2 - 4 - 1 -
3 - 4 - 1 - 2 -
3 - 4 - 2 - 1 -
1 - 3 - 2 - 4 -
1 - 3 - 4 - 2 -
1 - 2 - 3 - 4 -
1 - 2 - 4 - 3 -
1 - 4 - 3 - 2 -
1 - 4 - 2 - 3 -
2 - 3 - 1 - 4 -
2 - 3 - 4 - 1 -
2 - 1 - 3 - 4 -
2 - 1 - 4 - 3 -
2 - 4 - 3 - 1 -
2 - 4 - 1 - 3 -
4 - 3 - 1 - 2 -
4 - 3 - 2 - 1 -
4 - 1 - 3 - 2 -
4 - 1 - 2 - 3 -
4 - 2 - 3 - 1 -
4 - 2 - 1 - 3 -
Program exited normally.
(gdb)
Here, the program gives all the permutations for the set = {1,2,3,4}.
It's good but the only thing that I changed between the two functions
is the int * who becam a char *.
So, I don't know what is the probleme in the first version of
permutation with the int *.
Someone would have an idea of the problem who cause this error ?
Thanks for your help.
Sylvain. 9 1438
sylsau 写道: Hi,
I am doing a little program who calculates the permutation of a set of vertex. I use the recursivity for this calcul.
My function who calculate the permutations :
void permutation(set *e, int *current, int nbre) { set *p, *copie; int *tmp; int i;
if(e != NULL) { p = e;
tmp = realloc(current, sizeof *current *(nbre+1));
if(tmp == NULL) exit(-1); else current = tmp;
while(p != NULL) { copie = copie_elt(e); // the function copie_elt let to copy the set e and to return this copy current[nbre] = p->st; delete_elt(&copie,p->st); // this function let to delete an element of copie. The element who
// is associated with the value p->st permutation(copie,current,nbre+1); // call of permutation with the set reducted. p = p->suivant; }
}else{
// In current, we have stocked the current permutation, so we print it for(i=0; i<nbre; i++) printf("%d - ",current[i]);
printf("\n");
}
}
I call it in the main with :
/* initialization of the variable e */
permutation(set,current,0);
By executing the program, I have this on my screen (I tried to debug with GDB) :
(gdb) run
3 - 1 - 2 - 4 - *** glibc detected *** double free or corruption (fasttop): 0x0804a048 ***
Program received signal SIGABRT, Aborted. 0x4004ea27 in raise () from /lib/tls/libc.so.6
(gdb)
So, I tried this function with a char * for the variable current, the code gives it :
void permutation(set *e, char *current, int nbre) { set *p, *copie; char *tmp; int i;
if(e != NULL) { p = e;
tmp = realloc(current, sizeof *current *(nbre+1));
if(tmp == NULL) exit(-1); else current = tmp;
while(p != NULL) { copie = copie_elt(e); // the function copie_elt let to copy the set e and to return this copy current[nbre] = p->st; delete_elt(&copie,p->st); // this function let to delete an element of copie. The element who
// is associated with the value p->st permutation(copie,current,nbre+1); // call of permutation with the set reducted. p = p->suivant; }
}else{
// In current, we have stocked the current permutation, so we print it for(i=0; i<nbre; i++) printf("%d - ",current[i]);
printf("\n");
}
}
I call it in the main with :
permutation(e,current,0);
And there, the program gives the waited answer :
(gdb) run 3 - 1 - 2 - 4 - 3 - 1 - 4 - 2 - 3 - 2 - 1 - 4 - 3 - 2 - 4 - 1 - 3 - 4 - 1 - 2 - 3 - 4 - 2 - 1 - 1 - 3 - 2 - 4 - 1 - 3 - 4 - 2 - 1 - 2 - 3 - 4 - 1 - 2 - 4 - 3 - 1 - 4 - 3 - 2 - 1 - 4 - 2 - 3 - 2 - 3 - 1 - 4 - 2 - 3 - 4 - 1 - 2 - 1 - 3 - 4 - 2 - 1 - 4 - 3 - 2 - 4 - 3 - 1 - 2 - 4 - 1 - 3 - 4 - 3 - 1 - 2 - 4 - 3 - 2 - 1 - 4 - 1 - 3 - 2 - 4 - 1 - 2 - 3 - 4 - 2 - 3 - 1 - 4 - 2 - 1 - 3 -
Program exited normally. (gdb)
Here, the program gives all the permutations for the set = {1,2,3,4}. It's good but the only thing that I changed between the two functions is the int * who becam a char *.
So, I don't know what is the probleme in the first version of permutation with the int *. Someone would have an idea of the problem who cause this error ?
Thanks for your help.
Sylvain.
because the realloc() return a char* value,if you want to use like
this :
int * tmp;
tmp = realloc(current, sizeof *current *(nbre+1));
you must do a casting, write like this tmp = (char *)realloc(current,
sizeof *current *(nbre+1));
sylsau wrote: Hi,
I am doing a little program who calculates the permutation of a set of vertex.
Post the whole program.
--
pete us******@gmail.com wrote: because the realloc() return a char* value,if you want to use like this : int * tmp; tmp = realloc(current, sizeof *current *(nbre+1)); you must do a casting, write like this tmp = (char *)realloc(current, sizeof *current *(nbre+1));
I can't make sense out of that.
It almost seems as though you're saying that
realloc returns type char*, and that a (char*) cast
will somehow help you assign that return value
to an int* variable.
--
pete
"us******@gmail.com" <us******@gmail.com> writes:
[...] because the realloc() return a char* value,if you want to use like this : int * tmp; tmp = realloc(current, sizeof *current *(nbre+1)); you must do a casting, write like this tmp = (char *)realloc(current, sizeof *current *(nbre+1));
Wrong, and wrong.
realloc() returns a void*, which can be implicitly converted to any
pointer-to-object type (no cast is necessary or recommended).
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
THe whole program :
#include <stdio.h>
#include <stdlib.h>
typedef struct ensemble{
int st;
struct ensemble *suivant;
}ensemble;
void supprimer_elt(ensemble **e, int nbre)
/* supprime elt nbre de e */
{
ensemble *p, *prec;
prec = NULL;
p = *e;
while(p != NULL && p->st != nbre)
{
prec = p;
p = p->suivant;
}
if(prec == NULL) // on supprime l'elt de tete
*e = (*e)->suivant;
else
prec->suivant = p->suivant;
free(p);
}
ensemble *copie_elt(ensemble *e)
/* renvoie la copie de e */
{
ensemble *copie = NULL, *new, *p, *insertion;
if( e != NULL)
{
copie = copie_elt(e->suivant);
new = (ensemble *) malloc(sizeof *new);
new->st = e->st;
new->suivant = copie;
copie = new;
}
return copie;
}
void permut(ensemble *e, int *current, int nbre)
{
ensemble *p, *copie;
int i;
int *tmp;
if(e != NULL)
{
p = e;
tmp = realloc(current, sizeof *current *(nbre+1));
if(tmp == NULL) exit(-1)
else current = tmp;
while(p != NULL)
{
copie = copie_elt(e);
current[nbre] = p->st;
supprimer_elt(&copie,p->st);
permut(copie,current,nbre+1);
p = p->suivant;
}
}else{
for(i=0; i<nbre; i++)
printf("%d - ",current[i]);
printf("\n");
}
}
int main(int argc, char **argv)
{
ensemble *e1,*e2,*e3,*e4,*p,*copie;
int *res = NULL;
e1 = (ensemble *) malloc(sizeof *e1);
e2 = (ensemble *) malloc(sizeof *e2);
e3 = (ensemble *) malloc(sizeof *e3);
e4 = (ensemble *) malloc(sizeof *e4);
e1->st = 3;
e2->st = 1;
e3->st = 2;
e4->st = 4;
e1->suivant = e2;
e2->suivant = e3;
e3->suivant = e4;
e4->suivant = NULL;
permut(e1,res,0);
return 0;
}
sylsau wrote: THe whole program :
#include <stdio.h> #include <stdlib.h>
typedef struct ensemble{ int st; struct ensemble *suivant; }ensemble;
void supprimer_elt(ensemble **e, int nbre) /* supprime elt nbre de e */ { ensemble *p, *prec;
prec = NULL; p = *e;
while(p != NULL && p->st != nbre) { prec = p; p = p->suivant; }
if(prec == NULL) // on supprime l'elt de tete *e = (*e)->suivant; else prec->suivant = p->suivant;
free(p);
}
ensemble *copie_elt(ensemble *e) /* renvoie la copie de e */ { ensemble *copie = NULL, *new, *p, *insertion;
if( e != NULL) { copie = copie_elt(e->suivant); new = (ensemble *) malloc(sizeof *new); new->st = e->st; new->suivant = copie; copie = new;
}
return copie; }
void permut(ensemble *e, int *current, int nbre) { ensemble *p, *copie; int i; int *tmp;
if(e != NULL) { p = e;
tmp = realloc(current, sizeof *current *(nbre+1));
if(tmp == NULL) exit(-1) else current = tmp;
while(p != NULL) { copie = copie_elt(e); current[nbre] = p->st; supprimer_elt(&copie,p->st); permut(copie,current,nbre+1); p = p->suivant; }
}else{
for(i=0; i<nbre; i++) printf("%d - ",current[i]);
printf("\n");
}
}
int main(int argc, char **argv) { ensemble *e1,*e2,*e3,*e4,*p,*copie; int *res = NULL;
e1 = (ensemble *) malloc(sizeof *e1); e2 = (ensemble *) malloc(sizeof *e2); e3 = (ensemble *) malloc(sizeof *e3); e4 = (ensemble *) malloc(sizeof *e4);
e1->st = 3; e2->st = 1; e3->st = 2; e4->st = 4;
e1->suivant = e2; e2->suivant = e3; e3->suivant = e4; e4->suivant = NULL;
permut(e1,res,0);
return 0; }
Compiled as is, your program gives these warnings and errors:
foo.c: In function `copie_elt':
foo.c:35: warning: unused variable `p'
foo.c:35: warning: unused variable `insertion'
foo.c: In function `permut':
foo.c:64: syntax error before "else"
foo.c: In function `main':
foo.c:88: warning: unused variable `p'
foo.c:88: warning: unused variable `copie'
Unused variables, OK, missing ;??? Strange, does it compile for you?
Real problem: You are doing a recursive call to permut. In some levels
of recursion
you are reallocing a pointer (current) that other recursion levels
still have and use.
That results in them using freed memory.
-David
David Resnick wrote: sylsau wrote: THe whole program :
Real problem: You are doing a recursive call to permut. In some levels of recursion you are reallocing a pointer (current) that other recursion levels still have and use. That results in them using freed memory.
It looks to me like an attempted synthesis
of array and linked list techniques.
Permutating a small array is pretty simple,
but I've also been trying to permutate a linked list
and it's been confusing for me.
--
pete
pete <pf*****@mindspring.com> writes: Permutating a small array is pretty simple, but I've also been trying to permutate a linked list and it's been confusing for me.
(I believe that "permute", not "permutate", is the verb you are
looking for.)
I have an implementation, if I understand what you're talking
about :
/* Arranges R0...R1 into the lexicographically next greater
permutation. Returns true if successful.
If R0...R1 is already the lexicographically greatest
permutation of its elements (i.e. ordered from greatest to
smallest), arranges them into the lexicographically least
permutation (i.e. ordered from smallest to largest) and
returns false.
COMPARE with auxiliary data AUX is used to compare nodes. */
bool
ll_next_permutation (struct ll *r0, struct ll *r1,
ll_compare_func *compare, void *aux)
{
if (r0 != r1)
{
struct ll *i = ll_prev (r1);
while (i != r0)
{
i = ll_prev (i);
if (compare (i, ll_next (i), aux) < 0)
{
struct ll *j;
for (j = ll_prev (r1); compare (i, j, aux) >= 0; j = ll_prev (j))
continue;
ll_swap (i, j);
ll_reverse (ll_next (j), r1);
return true;
}
}
ll_reverse (r0, r1);
}
return false;
}
Of course there are prerequisites, but I suspect that you won't
have trouble figuring out what they are.
--
Go not to Usenet for counsel, for they will say both no and yes.
Ben Pfaff wrote: pete <pf*****@mindspring.com> writes:
Permutating a small array is pretty simple, but I've also been trying to permutate a linked list and it's been confusing for me. (I believe that "permute", not "permutate", is the verb you are looking for.)
I'm sure it is.
I have an implementation, if I understand what you're talking about:
/* Arranges R0...R1 into the lexicographically next greater permutation. Returns true if successful. If R0...R1 is already the lexicographically greatest permutation of its elements (i.e. ordered from greatest to smallest), arranges them into the lexicographically least permutation (i.e. ordered from smallest to largest) and returns false. COMPARE with auxiliary data AUX is used to compare nodes. */ bool ll_next_permutation (struct ll *r0, struct ll *r1, ll_compare_func *compare, void *aux) { if (r0 != r1) { struct ll *i = ll_prev (r1); while (i != r0) { i = ll_prev (i); if (compare (i, ll_next (i), aux) < 0) { struct ll *j; for (j = ll_prev (r1); compare (i, j, aux) >= 0; j = ll_prev (j)) continue; ll_swap (i, j); ll_reverse (ll_next (j), r1); return true; } }
ll_reverse (r0, r1); }
return false; }
Of course there are prerequisites, but I suspect that you won't have trouble figuring out what they are.
I'll see what I can do with it.
Thank you.
--
pete This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Allcomp |
last post by:
Hello,
I have seen something strange on a customer's computer.
It is a P4 3 GHz with 512 MB Ram running on a Win2K SP3
When he uses a part of my application, it is really slow (more than 10
sec...
|
by: Rob Ristroph |
last post by:
Hi,
It's pretty unhelpful to post "I have a huge piece of code that
crashes in strange places, what's the problem?" but that's basically
my problem and I really am at my wit's end.
The piece...
|
by: Martijn Remmen |
last post by:
I have developed a service which exposes a COM object. This service is
running perfect on Windows 2000 Server and Windows 2000 Professional
under the SYSTEM account.
When the service is...
|
by: Gary |
last post by:
I have an application that has been working just fine for a couple of years.
It queries a SQL database and returns some formatted data back to the client.
I have a new client, who has a larger...
|
by: Piedro |
last post by:
Can someone reproduce the following error?
I'm using the module at the bottom of my post to owner draw a menu
items, I call the module from a form like this:
Private Sub mnuOpen_DrawItem(ByVal...
|
by: Martin Joergensen |
last post by:
Hi,
I've encountered a really, *really*, REALLY strange error :-)
I have a for-loop and after 8 runs I get strange results...... I
mean: A really strange result....
I'm calculating...
|
by: r.z. |
last post by:
My program behaves very strange. I keep getting the following error:
'The instruction at "some address" referenced memory at "some address". The
memory could not be written"'
The program consists...
|
by: VijaKhara |
last post by:
Hi all,
I just write a very simple codes in C and vthere is a very strange bug
which I cannot figure out why.
The first loop is for v, and the second for k. There is no
relationship between v...
|
by: Jeff |
last post by:
Okay, I'm still new to vb.net 2005 - throught this was a hardware problem,
but now I don't know.
(I'm having some problem with my newgroup provider, so hopefully this will
go through)
This...
|
by: angryRotarian |
last post by:
Im trying to write a MPI C program for a debian cluster that multiplies matricies. Ive written almost all of it, but cant seem to shake a strange problem. Here is the code:
#include <stdio.h>...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
| |