Pages: [1]   Go Down
Author Topic: Compare Two Arrays of Different Lengths and Return the Common Values  (Read 1006 times)
0 Members and 1 Guest are viewing this topic.
Offline Offline
Newbie
*
Karma: 0
Posts: 2
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I'd like to define a function that compares two arrays with differing lengths and returns the values common to both arrays. Can anyone help me with how that will be written? Thanks.
Logged

Pittsburgh, PA, USA
Offline Offline
Faraday Member
**
Karma: 98
Posts: 4819
I learn a bit every time I visit the forum.
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

How would you do it if it was two lists of letters or numbers on paper?

Let's say letters and these are the lists:

A B C D A B C D

A A C D C B A B C A D D D

Would you start with the first letter of the first list and find a match in the second list?
And if you do, will you record that?
Will you remove the matched letter in the second list so it doesn't get matched again?
And then on to the next letter in the first list? And the next till it's done?

Just how... sorry but I won't write your code. But I will suggest modeling the actions and playing with for-next and while loops and keeping information in variables before deciding what to write.

Logged

I find it harder to express logic in English than in Code.
Sometimes an example says more than many times as many words.

NE PA
Offline Offline
Full Member
***
Karma: 5
Posts: 156
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

I don't know if there is an easier way but with two for loops, one inside the other, you can compare the contents of one array with another.

Something like this:
For loop i
   For loop j
       If i equals j
           do something
       }
   }
}

That is pseudo code but you get the idea.

      
Logged


Sydney, Australia
Offline Offline
Edison Member
*
Karma: 33
Posts: 1285
Big things come in large packages
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Just to add another question:

Are the lists sorted in order? That would allow the matching to be more efficient
Logged

Arduino libraries http://arduinocode.codeplex.com
Parola hardware & library http://parola.codeplex.com

Seattle, WA USA
Offline Offline
Brattain Member
*****
Karma: 644
Posts: 50507
Seattle, WA USA
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Do you mean when the ith element in one array matches the ith element in the other array, or do you mean when the ith element in one array matched any element in the other array?
Logged

Pittsburgh, PA, USA
Offline Offline
Faraday Member
**
Karma: 98
Posts: 4819
I learn a bit every time I visit the forum.
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Each array in ascending or descending order. Because then you'd know when to stop iterating the match search.

Unless I miss my guess, elements of both arrays may or may not have matches.

Logged

I find it harder to express logic in English than in Code.
Sometimes an example says more than many times as many words.

Sydney, Australia
Offline Offline
Edison Member
*
Karma: 33
Posts: 1285
Big things come in large packages
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Correct guess. I think that if both lists are sorted within themselves it is possible to do the task with a single pass through the lists.
Logged

Arduino libraries http://arduinocode.codeplex.com
Parola hardware & library http://parola.codeplex.com

Offline Offline
Newbie
*
Karma: 0
Posts: 2
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

So I've come up with something like this
Code:
int  common_elements(int a[], int b[]){
 
a.sort();
b.sort();
n, o = 0, 0;
common = [];
while n < len(a) and 0 < len(b):

if a[n] == b[o]
{
  common.append(a[i]);
  n += 1;
  o += 1;
}
if (a[n] < b[o])
{
  n += 1;
else
{
  o += 1;
}
}

I think I've got something wrong with the types as it fails to compile with this error. Anyone wanna point out any errors, I'm not that experienced with C code. Thanks
Code:
reguest for member 'sort' in 'a'. which is of non-class type 'int*'

A little more data on the input. One string contains 7 fixed numbers and the other contains three fixed numbers. I want to find the common numbers in the two arrays in order to iterate though a couple sets of color and pinout data
« Last Edit: January 25, 2013, 01:59:28 pm by tx0rx0 » Logged

Offline Offline
Edison Member
*
Karma: 33
Posts: 1470
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Arrays don't have an automatic sorting operator, you must use qsort() or write your own.

This is not C++. You will have to rework a lot!

common = [] ???

you need parens for the while statement and no colon.

you need parens in your if statement

and so on.
Logged

UK
Offline Offline
Shannon Member
****
Karma: 223
Posts: 12630
-
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Unless you have a particular need for this to run as fast as possible, for arrays that small I wouldn't bother sorting them and would just brute-force compare the unsorted arrays element by element.

for each element in left array
    for each element in right array
        if left == right
            append to results

If you want the results to be unique and the input arrays are not unique then I'd implement the append operation in a function that checked the new result against the values already in the result array.
               
Logged

I only provide help via the forum - please do not contact me for private consultancy.

Pittsburgh, PA, USA
Offline Offline
Faraday Member
**
Karma: 98
Posts: 4819
I learn a bit every time I visit the forum.
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

This is C++ but you have to use a container class (hope you've got the RAM) to get that sort.
But honestly, it's more work to sort the arrays than to simply find matches.

Also OP, learn to use pointers and pass those to your functions. Pointers are like using web links except for RAM. They're just address holders with names that know the size variable they point to. You ++ a pointer, it points to the next variable in your array. The array name is itself a pointer to the start of the array.

byte  array[ 20 ];
byte *a = array; // now *a points to the beginning of array[ 20 ]

There's a very few steps to learn that you can pick up between examples and explanations.

Work the steps out with pencil and paper or keyboard and editor. Understanding what you're doing will in the end show you how simple the basis is and no magic pill class function will ever do that. In fact, magic pill functions is a great way to **never learn** how simple these things work which means for the next and next problem the answer will be finding more magic pills.

C is really very simple at heart. So is any alphabet. What you do with either can make the complexity. You don't need to include all of Crime and Punishment to refer to beating a dead horse.
Logged

I find it harder to express logic in English than in Code.
Sometimes an example says more than many times as many words.

Pages: [1]   Go Up
Jump to: