Help with 1 function

This is a discussion on Help with 1 function within the C Programming forums, part of the General Programming Boards category; Ok, I got delete and some of the functions running after a long time..I have one more function left and ...

  1. #1
    Registered User
    Join Date
    Jul 2010
    Posts
    5

    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.

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,667
    Cast the divisor as double to do floating point division.

  3. #3
    Registered User
    Join Date
    Jul 2010
    Posts
    5
    Quote Originally Posted by whiteflags View Post
    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.

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,667
    No, I said the divisor. The divisor is the thing you divide by; it is the bottom number in a fraction.

  5. #5
    Registered User
    Join Date
    Jul 2010
    Posts
    5
    Quote Originally Posted by whiteflags View Post
    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.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,650
    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.
    Last edited by laserlight; 08-15-2010 at 01:31 PM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Jul 2010
    Posts
    5
    Quote Originally Posted by laserlight View Post
    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?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,650
    Quote Originally Posted by TetsuoShima
    I'm supposed to state the time complexity for each function using Big-O notation..How would I go about doing that?
    Start by establishing the time complexity of those functions that are the building blocks for others
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling C in Visual Studio 2005
    By emanresu in forum C Programming
    Replies: 3
    Last Post: 11-16-2009, 03:25 AM
  2. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 02:07 AM
  3. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  4. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  5. const at the end of a sub routine?
    By Kleid-0 in forum C++ Programming
    Replies: 14
    Last Post: 10-23-2005, 06:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21