A* algorithm

[sulekhasweety]

Hi ,

this is the program showing implementation of a* algorithm, given n
integers and a sum m ,write a program to find the set of integers
summing to m using a* algorithm.

but i am not getting the o/p correct , i am getting only one set of
integers, can any one point the errors/corrections required ?

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef enum {FALSE,TRUE}bln;
int subsetsum(int*,int,int,bln* ,int);
int compare(void*,void*);
void printanswer(int*,int,bln*);
int main(void)
{

int a[] = {5,3,4,8,9,6};
int sum = 15;
int size = sizeof(a)/sizeof(int);
int i;

bln *selected = calloc(size,sizeof(bln));

qsort(a,size,sizeof(int),compare);

for(i=0;i < size;i++)
{
printf("\n i = %d",i);

if( subsetsum(a,size,sum,selected,i))
printanswer(a,size,selected);

memset(selected,FALSE,size);
}

return EXIT_SUCCESS;
}
int subsetsum(int *a,int n,int sum,bln *selected ,int start)
{

int i=start;

if(sum == 0)
return TRUE;

if(selected[i] == FALSE && a[i] <= sum)
{
selected[i] = TRUE;
if(subsetsum(a,n,sum - a[i],selected,i+1))
return TRUE;

selected[i] = FALSE;
}

return FALSE;

}

void printanswer(int* a,int n,bln* selected)
{
int i;

for(i=0;i<n;i++)
if(selected[i])
printf("\t%d",a[i]);

puts("");
}
int compare(void* e1,void* e2)
{
return *(int*)e2 - *(int*)e1;

}

[Barry Schwarz]

On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), su***********@gmail.com
wrote:

>Hi ,

this is the program showing implementation of a* algorithm, given n
integers and a sum m ,write a program to find the set of integers
summing to m using a* algorithm.

but i am not getting the o/p correct , i am getting only one set of
integers, can any one point the errors/corrections required ?

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef enum {FALSE,TRUE}bln;
int subsetsum(int*,int,int,bln* ,int);
int compare(void*,void*);
void printanswer(int*,int,bln*);
int main(void)
{

int a[] = {5,3,4,8,9,6};
int sum = 15;
int size = sizeof(a)/sizeof(int);

You would be better off using sizeof(*a) for the divisor.

int i;

bln *selected = calloc(size,sizeof(bln));

qsort(a,size,sizeof(int),compare);

Your compiler should have reported a problem. Your compare function
does not have the correct prototype to be used by qsort.

Also sizeof(*a) here for the third argument.

>
for(i=0;i < size;i++)
{
printf("\n i = %d",i);

if( subsetsum(a,size,sum,selected,i))
printanswer(a,size,selected);

memset(selected,FALSE,size);

This sets the first six bytes pointed to by selected to zero.
Unfortunately, you have no idea what type of integer selected points
to. Since you only want to store 0 and 1 in each of the integers, you
could make bln a typedef for char. Or you could change the third
argument to size * sizeof(*selected) which would reinitialize the
entire allocated array. As it stands now, if bln is not the same as
char, you are not resetting the entire array for the next set of
tests.

}

return EXIT_SUCCESS;
}
int subsetsum(int *a,int n,int sum,bln *selected ,int start)
{

int i=start;

if(sum == 0)
return TRUE;

if(selected[i] == FALSE && a[i] <= sum)
{
selected[i] = TRUE;
if(subsetsum(a,n,sum - a[i],selected,i+1))

It is possible to call subsetsum with start set to size-1. This
recursive call would then call subsetsum with start set to size and i
is then set to start and both selected[i] and a[i] attempt to evaluate
non-existent objects. This is called undefined behavior.

return TRUE;

selected[i] = FALSE;
}

return FALSE;

}

void printanswer(int* a,int n,bln* selected)
{
int i;

for(i=0;i<n;i++)
if(selected[i])
printf("\t%d",a[i]);

puts("");
}
int compare(void* e1,void* e2)
{
return *(int*)e2 - *(int*)e1;

}

Remove del for email

[Joachim Schmitz]

Barry Schwarz wrote:

On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), su***********@gmail.com
wrote:

<snip>

>int compare(void*,void*);

<snip>

> qsort(a,size,sizeof(int),compare);

Your compiler should have reported a problem. Your compare function
does not have the correct prototype to be used by qsort.

What's wrong with it? Besides the missing const?

Bye, Jojo

[sulekhasweety]

On Apr 5, 1:45*pm, Barry Schwarz <[e-mail]:

On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), [e-mail]
wrote:

Hi ,

this is the program showing implementation of a* algorithm, given n
integers and a sum m ,write a program to find the set of integers
summing to m using a* algorithm.

but i am not getting the o/p correct , i am getting only one set of
integers, can any one point the errors/corrections required ?

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef enum {FALSE,TRUE}bln;
int subsetsum(int*,int,int,bln* ,int);
int compare(void*,void*);
void printanswer(int*,int,bln*);

int main(void)
{

* int a[] *= {5,3,4,8,9,6};
* int sum *= 15;
* int size = sizeof(a)/sizeof(int);

You would be better off using sizeof(*a) for the divisor.

* int i;

* bln *selected = calloc(size,sizeof(bln));

* qsort(a,size,sizeof(int),compare);

Your compiler should have reported a problem. *Your compare function
does not have the correct prototype to be used by qsort.

Also sizeof(*a) here for the third argument.

* for(i=0;i < size;i++)
* {
* * printf("\n i = %d",i);

* * if( subsetsum(a,size,sum,selected,i))
* * *printanswer(a,size,selected);

* * memset(selected,FALSE,size);

This sets the first six bytes pointed to by selected to zero.
Unfortunately, you have no idea what type of integer selected points
to. *Since you only want to store 0 and 1 in each of the integers, you
could make bln a typedef for char. *Or you could change the third
argument to size * sizeof(*selected) which would reinitialize the
entire allocated array. *As it stands now, if bln is not the same as
char, you are not resetting the entire array for the next set of
tests.

* }

* return EXIT_SUCCESS;
}

int subsetsum(int *a,int n,int sum,bln *selected ,int start)
{

* int i=start;

* if(sum == 0)
* * return TRUE;

* if(selected[i] == FALSE && a[i] <= sum)
* {
* * *selected[i] = TRUE;
* * *if(subsetsum(a,n,sum - a[i],selected,i+1))

It is possible to call subsetsum with start set to size-1. *This
recursive call would then call subsetsum with start set to size and *i
is then set to start and both selected[i] and a[i] attempt to evaluate
non-existent objects. *This is called undefined behavior.

* * *return TRUE;

* * *selected[i] = FALSE;
* }

* return FALSE;

}

void printanswer(int* a,int n,bln* selected)
{
* *int i;

* *for(i=0;i<n;i++)
* * if(selected[i])
* * printf("\t%d",a[i]);

* *puts("");
}

int compare(void* e1,void* e2)
{
* *return *(int*)e2 - *(int*)e1;

}

I tried what u have said as follows , but still i am not get correct o/
p
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/*typedef enum {FALSE,TRUE}*/
char bln;
int subsetsum(int*,int,int,char* ,int);
int compare(void*,void*);
void printanswer(int*,int,char*);
int main(void)
{

int a[] = {5,3,4,8,9,6};
int sum = 15;
int size = sizeof(a)/sizeof(*a);
int i;

char *selected = calloc(size,sizeof(char));

qsort(a,size,sizeof(int),compare);

for(i=0;i < size;i++)
{
printf("\n i = %d",i);

if( subsetsum(a,size,sum,selected,i))
printanswer(a,size,selected);

memset(selected,0,size * sizeof(*selected));
}

return EXIT_SUCCESS;
}
int subsetsum(int *a,int n,int sum,char *selected ,int start)
{

int i=start;

if(sum == 0)
return 1;

if(selected[i] == 0 && a[i] <= sum)
{
selected[i] = 1;
if(subsetsum(a,n,sum - a[i],selected,i+1))
return 1;

selected[i] = 0;
}

return 0;

}

void printanswer(int* a,int n,char* selected)
{
int i;

for(i=0;i<n;i++)
if(selected[i])
printf("\t%d",a[i]);

puts("");
}
int compare(void* e1,void* e2)
{
return *(int*)e1 - *(int*)e2;

}

I am getting o/p as follows:-

i = 0
i = 1 4 5 6

i = 2
i = 3
i = 4
i = 5

[Barry Schwarz]

On Sat, 5 Apr 2008 12:06:33 +0200, "Joachim Schmitz"
<no*********@schmitz-digital.dewrote:

>Barry Schwarz wrote:

>On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), su***********@gmail.com
wrote:

<snip>

>>int compare(void*,void*);

<snip>

>> qsort(a,size,sizeof(int),compare);

Your compiler should have reported a problem. Your compare function
does not have the correct prototype to be used by qsort.

What's wrong with it? Besides the missing const?

Isn't that enough?
Remove del for email

[Barry Schwarz]

On Sat, 5 Apr 2008 09:00:39 -0700 (PDT), su***********@gmail.com
wrote:
snip 120+ lines of obsolete code

Please trim your posts when replying

>
I tried what u have said as follows , but still i am not get correct o/
p
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/*typedef enum {FALSE,TRUE}*/
char bln;
int subsetsum(int*,int,int,char* ,int);
int compare(void*,void*);
void printanswer(int*,int,char*);
int main(void)
{

int a[] = {5,3,4,8,9,6};
int sum = 15;
int size = sizeof(a)/sizeof(*a);
int i;

char *selected = calloc(size,sizeof(char));

qsort(a,size,sizeof(int),compare);

I said your compare function was wrong. It is still wrong. If you
don't care why should I?

>
for(i=0;i < size;i++)
{
printf("\n i = %d",i);

if( subsetsum(a,size,sum,selected,i))
printanswer(a,size,selected);

memset(selected,0,size * sizeof(*selected));
}

return EXIT_SUCCESS;
}
int subsetsum(int *a,int n,int sum,char *selected ,int start)
{

int i=start;

if(sum == 0)
return 1;

if(selected[i] == 0 && a[i] <= sum)
{
selected[i] = 1;
if(subsetsum(a,n,sum - a[i],selected,i+1))

This will still invoke undefined behavior when i in main is size-1.
You haven't addressed that issue at all.

return 1;

selected[i] = 0;
}

There is an error in the logic of this if block. It needs to be a
loop. The net effect of the error is that subsetsum can only detect a
solution when using sequential elements of a. That is why it catches
4-5-6 when i is 1 in main but does not catch 3-4-8 when i is 0 or 6-9
when i is 3. Take a sheet of paper and "play computer" to see it
happen.

>
return 0;

}

void printanswer(int* a,int n,char* selected)
{
int i;

for(i=0;i<n;i++)
if(selected[i])
printf("\t%d",a[i]);

puts("");
}
int compare(void* e1,void* e2)
{
return *(int*)e1 - *(int*)e2;

}

I am getting o/p as follows:-

i = 0
i = 1 4 5 6

i = 2
i = 3
i = 4
i = 5

Remove del for email

[Joachim Schmitz]

Barry Schwarz wrote:

On Sat, 5 Apr 2008 12:06:33 +0200, "Joachim Schmitz"
<no*********@schmitz-digital.dewrote:

>Barry Schwarz wrote:

>>On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), su***********@gmail.com
wrote:

<snip>

>>>int compare(void*,void*);

<snip>

>>> qsort(a,size,sizeof(int),compare);

Your compiler should have reported a problem. Your compare function
does not have the correct prototype to be used by qsort.

What's wrong with it? Besides the missing const?

Isn't that enough?

Maybe, but why didn't you say so rather than let us guess?

Bye, Jojo

[Joachim Schmitz]

Barry Schwarz wrote:

On Sat, 5 Apr 2008 09:00:39 -0700 (PDT), su***********@gmail.com
wrote:
snip 120+ lines of obsolete code

Please trim your posts when replying

>>
I tried what u have said as follows , but still i am not get correct
o/ p
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/*typedef enum {FALSE,TRUE}*/
char bln;
int subsetsum(int*,int,int,char* ,int);
int compare(void*,void*);
void printanswer(int*,int,char*);
int main(void)
{

int a[] = {5,3,4,8,9,6};
int sum = 15;
int size = sizeof(a)/sizeof(*a);
int i;

char *selected = calloc(size,sizeof(char));

qsort(a,size,sizeof(int),compare);

I said your compare function was wrong. It is still wrong. If you
don't care why should I?

You hadn't said where it was wrong and still don't bother to.
To the OP:
int compare(const void*, const void*);

Bye, Jojo

[sulekhasweety]

Here is the corrected program

#include< stdio.h >
#include< stdlib.h >
#include< string.h >
char bln;
int subsetsum(int*,int,int,char* ,int);
int compare(const void*,const void*);
void printanswer(int*,int,char*);
int main(void)
{

int a[] = {5,3,4,8,9,6};
int sum = 15;
int size = sizeof(a)/sizeof(*a);
int i;
char *selected = calloc(size,sizeof(*selected));

qsort(a,size,sizeof(int),compare);

for(i=0;i < (size-1);i++)
{
printf("\n i = %d",i);

if( subsetsum(a,size,sum,selected,i))
printanswer(a,size,selected);

memset(selected,0,size * sizeof(*selected));
}

return EXIT_SUCCESS;
}
int subsetsum(int *a,int n,int sum,char *selected ,int start)
{
int i;

if(sum == 0)
return 1;

for(i=start;i <= (n-1);i++)
if(selected[i] == 0 && a[i] <= sum)
{
selected[i] = 1;
if(subsetsum(a,n,sum - a[i],selected,i+1))
return 1;

selected[i] = 0;
}

return 0;
}

void printanswer(int* a,int n,char* selected)
{
int i;

for(i=0;i< n;i++)
if(selected[i])
printf("\t%d",a[i]);

puts("");
}
int compare(const void* e1,const void* e2)
{
return *(int*)e2 - *(int*)e1;
}

[Barry Schwarz]

On Sun, 6 Apr 2008 09:17:42 +0200, "Joachim Schmitz"
<no*********@schmitz-digital.dewrote:

>Barry Schwarz wrote:

>On Sat, 5 Apr 2008 12:06:33 +0200, "Joachim Schmitz"
<no*********@schmitz-digital.dewrote:

>>Barry Schwarz wrote:
On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), su***********@gmail.com
wrote:
<snip>
int compare(void*,void*);
<snip>
qsort(a,size,sizeof(int),compare);

Your compiler should have reported a problem. Your compare function
does not have the correct prototype to be used by qsort.
What's wrong with it? Besides the missing const?

Isn't that enough?

Maybe, but why didn't you say so rather than let us guess?

Because spoon feeding is not conducive to learning. He didn't ask why
he got a diagnostic message he didn't understand. He asked why his
code wasn't producing the expected results. Two reasonable first
steps are to remove the undefined behavior and generate a clean
compile.

If he looked up qsort and checked the prototype, the lesson would stay
with him a lot longer. Or at least he will improve his skill in
looking it up. And maybe also figure out how to get his compiler to
warn him if he makes a similar mistake again.
Remove del for email

[Barry Schwarz]

On Sun, 6 Apr 2008 04:46:27 -0700 (PDT), su***********@gmail.com
wrote:

>Here is the corrected program

It looks much better.

>#include< stdio.h >
#include< stdlib.h >
#include< string.h >
char bln;
int subsetsum(int*,int,int,char* ,int);
int compare(const void*,const void*);
void printanswer(int*,int,char*);
int main(void)
{

int a[] = {5,3,4,8,9,6};
int sum = 15;
int size = sizeof(a)/sizeof(*a);
int i;
char *selected = calloc(size,sizeof(*selected));

qsort(a,size,sizeof(int),compare);

for(i=0;i < (size-1);i++)
{
printf("\n i = %d",i);

if( subsetsum(a,size,sum,selected,i))
printanswer(a,size,selected);

memset(selected,0,size * sizeof(*selected));
}

A style suggestion which will save you a lot of aggravation later
(when you write larger programs). Learn to indent consistently. I
prefer 3 or 4 spaces (not tabs if you post to Usenet) but the
consistency is more important than the value (within reason). This
block should look something like
for
{
printf
if
printanswer
memset
}
It lets you quickly recognize the range of loops and if statements.

>
return EXIT_SUCCESS;
}
int subsetsum(int *a,int n,int sum,char *selected ,int start)
{
int i;

if(sum == 0)
return 1;

for(i=start;i <= (n-1);i++)

Using size-1 in main and n-1 here eliminates the undefined behavior at
the cost of not handling boundary conditions (also known as extreme
cases or corner conditions). Try the same program with sum set 3.

You should also try with sum set to 4 or 7 and decide how you want to
clean up the output. (Hint: one solution would be a simple if in
front of the call to printanswer.)

>if(selected[i] == 0 && a[i] <= sum)
{
selected[i] = 1;
if(subsetsum(a,n,sum - a[i],selected,i+1))
return 1;

selected[i] = 0;
}

return 0;
}

void printanswer(int* a,int n,char* selected)
{
int i;

for(i=0;i< n;i++)
if(selected[i])
printf("\t%d",a[i]);

for
if
printf

>
puts("");
}
int compare(const void* e1,const void* e2)
{
return *(int*)e2 - *(int*)e1;

Many lint type programs will complain that you are casting away the
const. Chang the two casts to (const int*), even though technically
unnecessary (especially in this case with such a simple function),
would eliminate that.

Just for your info, the above is not completely safe in that it could
result in overflow. Since your real purpose is the algorithm and not
the sort, I wouldn't change it but the usual recommendation is

const int *i2 = e2;
const int *i1 = e1;
return (*i1 *i2) ? (-1) : (*i1 < *i2);
(parentheses just for clarity)

I wonder why you changed from an ascending sort to a descending one.

>}

Remove del for email