Thread: Equality of 2 Arrays

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    23

    Equality of 2 Arrays

    Hi guys. I am having trouble with checking equality of 2 Arrays which have integers.. At first it sounded easy, but for some unknown reason, I'm finding it hard to code. I don't want to sort out the arrays first..

    Code:
    int A[11]={1,7,5,7,4,3,5,2,1,9,8};
    
    int B[11]={9,8,1,2,3,5,1,5,7,7,4};
    
    for(int i=0;i<11;i++)
    {
    	for(int j=0;j<11;j++)
    	{
    	             if (A[i]==B[j])
                   		   return true;
    	 }
    
    }
    I know this doesn't work.. Haha.. Can anyone give me some ideas on how to solve this. I thought this was supposed to be easy but I'm struggling!! Thanks!

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Proposition: the two arrays are equal, where "equal" means that each corresponding element is equal. Simultaneously iterate over the arrays to find a counter example, i.e., corresponding elements that are not equal. If you cannot find such a counterexample, then you have proven the proposition to be true by exhaustive consideration of cases.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    in this case if you are only comparing 'corresponding' elements then only one loop is required...

  4. #4
    Registered User
    Join Date
    Oct 2009
    Posts
    23
    Maybe I used the wrong term. I want to check whether both array contain the same elements.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by 7heavens
    I want to check whether both array contain the same elements.
    Sort, then it's business as usual. (Unless you want to remove duplicates, in which case you remove them after sorting as they would be clumped together, making them easier to detect.)
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Oct 2009
    Posts
    23
    Is there a way to do it without sorting the arrays?

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Of course. For example, you could iterate over one array and attempt to find a corresponding element in the other array. If no such element is found, you know the arrays are not equal.

    You need to be careful though: what exactly do you mean by "both array contain the same elements"? For example, is an array that contains only one element, which has the value of 123, equal to an array containing two elements, both of which have the value of 123? They contain the same elements, but they are not of the same size.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Or you can use std::map to count how many times values occur in either array and then compare the maps.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  9. #9
    Registered User
    Join Date
    Oct 2009
    Posts
    23
    Thank you for the prompt responses laserlight. What I meant by both array contain the same elements is that the size of both the array is the same and they contain the same elemenets but not necessarily in order. For example, int A[]={1,2,3} and int B[]={3,1,2} contains the same elements. Got the algorithm already. Here's my code. =)

    Code:
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    bool equality ( int A[], int B[],int size)
    {
    	for(int x=0; x<size; x++)
    	{  
    		bool alreadyPresent = false;  
    		for(int y=0; y<size; ++y)
    		{		
    			if(A[x] == B[y])
    				alreadyPresent =  true;
    		}
    		if (alreadyPresent==false)
    			return false;
    	}
    	return true;
    }
    
    int main()
    {
    
    	int A[]={1,2,3,4,5};
    	int B[]={5,4,1,3,2};
    	cout << equality(A,B,5) <<endl;
    	
    }

  10. #10
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Your logic is flawed. You only test if the elements from A are present in B, not how many of each there are or if B has elements not present in A. Test your code with
    Code:
    int A[]={1,1,1,1,2};
    int B[]={1,2,2,2,2};
    Code:
    int A[]={1,1,1,1,1};
    int B[]={1,2,3,4,5};
    Not equal, but your code says they are.

  11. #11
    Registered User
    Join Date
    Oct 2009
    Posts
    23

    Smile

    Haha.. Yeah. Was about to post about that. What can I do to the code to make it work? I don't want to sort..

  12. #12
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Use an STL multiset. Initialize two different multiset containers with the data from the arrays and then just return container1 == container2. That's like 2 or 3 lines of code.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  13. #13
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by hk_mp5kpdw View Post
    Use an STL multiset. Initialize two different multiset containers with the data from the arrays and then just return container1 == container2. That's like 2 or 3 lines of code.
    Even though this is easy from a coding perspective, it constructs a rather elaborate data structure in memory.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  14. #14
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by brewbuck View Post
    Even though this is easy from a coding perspective, it constructs a rather elaborate data structure in memory.
    Indeed. It would be easier to create copies of both arrays. Then, working with the copies, sort and compare.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  15. #15
    Registered User
    Join Date
    Oct 2009
    Posts
    23
    I finally figured it out! =) I wanted to do it without sorting.. I hope this time I'm correct. I spent quite a lot of time on this!! Tried the test cases Mike posted and other test cases.. If there's anything wrong, do let me know. Thank you for all the responses. Here is my code. It assumes that the array doesn't have -1 as an element.. I think the code is pretty self-explanatory..


    Code:
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    
    bool equality( int A[],int B[], int size)
    {
    	int *p=new int[size];
    	for (int i=0;i<size;i++)
    	{
    		p[i]=B[i];
    	}
    	for(int i=0;i<size;i++)
    	{
    		bool found=false;
    		for(int j=0;j<size;j++)
    		{
    			if(A[i]==p[j])
    			{
    				p[j]=-1;
    				found=true;
    				break;
    			}
    		}
    		if (found==false)
    			return found;
    	}
    	return true;
    }
    
    
    
    
    int main()
    {
    int A[]={1,1,1,2,1,1};
    int B[]={1,1,2,1,1,1};
    
    
    
    	cout << equality(A,B,6)<<endl;
    	return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to create and manipulate Terabyte size Arrays with Win32API
    By KrishnaPG in forum Windows Programming
    Replies: 1
    Last Post: 11-05-2009, 04:08 AM
  2. pointers & arrays and realloc!
    By zesty in forum C Programming
    Replies: 14
    Last Post: 01-19-2008, 04:24 PM
  3. Replies: 16
    Last Post: 01-01-2008, 04:07 PM
  4. Need Help With 3 Parallel Arrays Selction Sort
    By slickwilly440 in forum C++ Programming
    Replies: 4
    Last Post: 11-19-2005, 10:47 PM
  5. Crazy memory problem with arrays
    By fusikon in forum C++ Programming
    Replies: 9
    Last Post: 01-15-2003, 09:24 PM