Thread: Help with 1 function

Ok, I got delete and some of the functions running after a long time..I have one more function left and it's racking my brain I can't figure it out.

The function I'm having trouble with is: Set_Similarity.

I'll give you all my code with the main function so you guys can just copy and paste it without having to create sets:

set.h

Code:

#ifndef SET_H__
#define SET_H__

typedef enum boolean { FALSE, TRUE } Boolean;

typedef int SetEntry;

typedef struct set
{
	
	int count; 
	SetEntry arrValue[50];
    
} Set;


void     Set_Create        (Set* set);
void     Set_Clear         (Set* set);
int      Set_Size          (const Set* set);
Boolean  Set_Empty         (const Set* set);

Boolean  Set_Insert        (Set* set, SetEntry value);
Boolean  Set_Delete        (Set* set, SetEntry value);
Boolean  Set_Contains      (const Set* set, SetEntry value);

void     Set_Union         (const Set* set1, const Set* set2, Set* ret);
void     Set_Intersection  (const Set* set1, const Set* set2, Set* ret);

double   Set_Similarity    (const Set* set1, const Set* set2);

void     Set_Print         (const Set* set);

#endif

set.c

Code:

#include "set.h"
#include <stdio.h>
#include <stdlib.h>

int main(void){
	
	Set helloSet;
	Set *pointer = &helloSet;
	Set_Create(pointer);
	Set byeSet;
	Set *ptr = &byeSet;
	Set_Create(ptr);
	Set ret;
	Set *rett = &ret;
	Set_Create(rett);
	//printf("%d\n", Set_Size(pointer));
    Set_Insert(pointer,10);
	Set_Insert(pointer,8);
	Set_Insert(pointer,27);
	Set_Insert(pointer,6);
	Set_Insert(ptr, 10);
	Set_Insert(ptr, 22);
	Set_Insert(ptr, 2);
	Set_Insert(ptr, 6);
	Set_Insert(ptr, 1);
	//Set_Intersection(pointer, ptr, rett);
	//printf("%d\n", Set_Size(pointer));
	//Set_Insert(pointer,2);
	//printf("%d\n", Set_Size(pointer));
	Set_Print(rett);
	printf("%g", Set_Similarity(pointer, ptr));
	return 0;
}
//This function creates a set and initalizes everything in it. Set should be empty
void Set_Create(Set* set)
{	
	if(set != NULL)
	{

		set->count = 0;

	}

}
//This function removes every element inside the set resulting in an empty set
void Set_Clear(Set* set)
{
	if(set != NULL)
	{

		set->count = 0;

	}

}
//This function returns the number of elements in the set
int Set_Size(const Set* set)
{
	if(set != NULL){

		return set->count;
	}
	
    return -1;
}
//This function returns true if the set is empty, otherwise it returns false
Boolean Set_Empty(const Set* set)
{
	if(set->count == 0)
	{

		return TRUE;
	}

	else
	{

		return FALSE;
	}

}
//This function inserts a new value in the set. It must also ensure that duplicate values will not be inserted
Boolean Set_Insert(Set* set, SetEntry value)
{
	if(set != NULL)
	{

		if(!Set_Contains(set, value))
		{

			set->arrValue[set->count]= value;
			set->count++;
			return TRUE;

		}

	}

    return FALSE;
}
//This function removes a value from the set
Boolean Set_Delete(Set* set, SetEntry value)
{
	int i,x;
	if(set!= NULL){

		if(Set_Contains(set, value))
		{

			for(i=0; i<set->count;i++)
			{

				if(set->arrValue[i]==value)
				{

					for(x=i;x<set->count;x++)
					{
						set->arrValue[i] =  set->arrValue[i+1];
					}

				}

			}

			set->count--;
		}

	}

    return FALSE;
}
//This function checks whether a value exists in a set
Boolean Set_Contains(const Set* set, SetEntry value)
{
	int i;
	for(i=0; i<set->count;i++)
	{

			if(set->arrValue[i] == value)
			{
				return TRUE;
			}
		

		}

    return FALSE;
}
//This function computes the union of 2 sets
void Set_Union(const Set* set1, const Set* set2, Set* ret)
{
	int i, x;
	for(i=0; i<set1->count; i++)
	{

		for(x=0; x<set2->count; x++)
		{

			if(set1->arrValue[i] != set2->arrValue[x])
			{
				Set_Insert(ret, set1->arrValue[i]);
				Set_Insert(ret, set2->arrValue[x]);
			}

		}

	}
	
}
//This function computes the intersection of 2 sets
void Set_Intersection(const Set* set1, const Set* set2, Set* ret)
{
	int i, x;
	for(i=0; i<set1->count; i++)
	{
		for(x=0; x<set2->count; x++)
		{
			if(set1->arrValue[i] == set2->arrValue[x])
			{
				Set_Insert(ret, set2->arrValue[i]);
			}

		}

	}

}
//This function computes the similiarity of 2 sets
double Set_Similarity(const Set* set1, const Set* set2)
{	
	Set simSet;
	Set *ptrsimSet = &simSet;
	Set_Create(ptrsimSet);
	
	Set simSet2;
	Set *ptrsimSet2 = &simSet2;
	Set_Create(ptrsimSet2);

    Set_Union(set1, set2, ptrsimSet);
	Set_Intersection(set1, set2, ptrsimSet2);

	int simSetSize = ptrsimSet->count;
	int simSet2Size = ptrsimSet2->count;
	
	double setDivision = simSetSize/simSet2Size;

	return setDivision;

}
//This function prints the contents of a set
void Set_Print(const Set* set)
{

	int i;
	for(i=0; i<set->count;i++)
	{
		printf("%d\n", set->arrValue[i]);
	}

}

The description for Set_Similarity is this:

We can measure how similar two sets are by dividing the size of their intersection by the size of their
union. The result is a value between 0 and 1, inclusive. If the sets are identical, then their intersection
will be the same as their union, so their similarity measure will be 1. If the sets have no elements in
common, then their intersection will be empty, so the similarity measure will be 0. If the sets are not
identical but have some elements in common, their similarity measure will fall somewhere between 0
and 1. For example, given A and B as defined above, we have:
similarity(A, B) = |A?B| / |A?B| = 3 / 9 = 0.333333

I keep getting 3?

Hopefully you guys can help..this is the last function.

Cast the divisor as double to do floating point division.

Originally Posted by whiteflags

Cast the divisor as double to do floating point division.

You mean like this?

double setDivision = (double)simSetSize/simSet2Size;

I ended up getting 3.5..

I'm supposed to get a number between 0 and 1. I'm trying to get the size of the union, and then the size of the intersection, then divide the 2 sizes.

Here's the description for what Set_Similarity is supposed to do:

This function computes the similarity between two sets. The similarity of the sets is given by the
size of their intersection divided by the size of their union. The parameters set1 and set2 are the
inputs. These sets must not be modified by this function. The function should return the similarity
as a double-precision floating point value.

No, I said the divisor. The divisor is the thing you divide by; it is the bottom number in a fraction.

Originally Posted by whiteflags

No, I said the divisor. The divisor is the thing you divide by; it is the bottom number in a fraction.

double setDivision = simSetSize/(double)simSet2Size;?

Sorry - I'm very new at C and not too sure what I'm doing wrong.

I cast the divisor as a double but it's still giving me 3.5.

Originally Posted by laserlight

It looks like you are dividing the union set size by the intersection set size instead of the other way round. Personally, I might write it as:

Code:

double Set_Similarity(const Set* set1, const Set* set2)
{	
    Set unionSet;
    Set_Create(&unionSet);

    Set intersectionSet;
    Set_Create(&intersectionSet);

    Set_Union(set1, set2, &unionSet);
    Set_Intersection(set1, set2, &intersectionSet);

    return (double)intersectionSet.count / unionSet.count;
}

EDIT:
Come to think about it: you should check that the union set is not an empty set.

Thanks!! It worked, really appreciate it.

Just one last thing..I'm supposed to state the time complexity for each function using Big-O notation..How would I go about doing that?