Simple array comparison

[jigglywiggly]

So basically I want to just create a method that compares two arrays and at the end tells me how many of them are the same, except I am having some issues...


Here is my code

package sigh;
import java.util.*;
public class Lovelyness {
    int counter=0;
    LinkedList linkedlist = new LinkedList();
    /** Creates a new instance of Lovelyness */
    public Lovelyness() {
    }

    public void commonElementsIteratively( int a[], int b[]) {

    for(int i =0; i<b.length; i++) {
        for(int j =0; j<a.length; j++) {
            if(b[i]==a[j]) {
                b[i]=(int)Math.random();
                a[j]=(int)Math.random();
                counter++;

            }
        }
    }

But it produces odd results, so for this input

        Lovelyness j = new Lovelyness();
        int[] a = new int[8];
        int[] b = new int[6];

        a[0]=1;
        a[1]=2;
        a[2]=2;
        a[3]=2;
        a[4]=5;
        a[5]=5;
        a[6]=6;
        a[7]=1;


        b[0]=0;
        b[1]=1;
        b[2]=1;
        b[3]=2; 
        b[4]=5;
        b[5]=2;


        j.commonElementsIteratively(a,b);

I get 9...

[CodesAway]

Let me clarify the goal. Given two arrays, you want to return the number of elements which are shared. Does the order matter?

For example, given your input, I get a count of 5, is that what you expected?

int[] a = {1, 2, 2, 2, 5, 5, 6, 1};
int[] b = {0, 1, 1, 2, 5, 2};
	 
// a[0] = b[1] (1)
// a[1] = b[3] (2)
// a[2] = b[5] (3)
// a[3] ------
// a[4] = b[4] (4)
// a[5] ------
// a[6] ------
// a[7] = b[2] (5)
	 
// Count = 5

If I'm understanding the problem, then my next question is why did you choose your current algorithm?

[Fubarable]

Let me clarify the goal....

I think that the original poster (OP) needs to clarify this. To the OP: please post your assignment verbatim.

[jigglywiggly]

It is just to see how many elements in both arrays do they share? Like if 2 is in both, it would count that as one.
Anyway

Given two arrays, find the number of elements of the first one that are also members of the second array. The elements in both arrays are sorted.
int commonElementsIteratively( int a[], int n, int b[], int m)
int commonElementsRecursively( int a[], int n, int b[], int m)
n is the number of elements in a and m contains the number of elements in b. Each function, independently, computes the number of elements of a that are members of b. The first function uses loops to do its work while the second one uses recursion for this purpose. Since the elements are sorted, both solutions should run in linear time with respect to the sum of n and m. It is okay for you to change the signature of the recursive function if you find it useful to do so.

int sumIteratively( int a[], int n)
int sumRecursively( int a[], int n)


I got rid of the length inputs this was originally for C++ I beleive.
int commonElementsIteratively( int a[], int n, int b[], int m)
int commonElementsRecursively( int a[], int n, int b[], int m)

I will do this Recursively after I do this simple for loop thing, it shouldn't be hard at all, I am just getting a bit of a brain freeze?

[CodesAway]

Ok, so the arrays are originally sorted. I was wondering if you were going to need to copy the data and sort the copy, but it seems the prof is making it easier for you.

I've never done this recursively, so I'll be learning at the same time as you, but I'm very familiar with the iterative approach, and have already a working solution. However, my solution might be different than what you were taught. So, I'll begin by asking, how you would approach this? Also, for your example, is the answer I gave the answer you were expecting? I'm big on verification, so I don't want to lead you toward a solution until I know that my solution meets what your needs.


Today, I'm going to look at apartments, so sadly, I won't be available to give feedback, but I'll start by giving advice, and I'm sure someone else on the forums will respond and assist you.


The fact that the arrays are sorted is a BIG hint on the solution. In fact, if they weren't sorted, sorting them would have been the first move. Sorting the data "aligns" it (hint hint).

For example, given your above example, sorted, you get this.

int[] a = { 1, 1, 2, 2, 2, 5, 5, 6 };
int[] b = { 0, 1, 1, 2, 2, 5 };

Think of how having the data sorted makes it easier to notice which values appear in both arrays. Before you code, figure out how you (as a human) would check which values are in both arrays. Then, once you have an idea of the algorithm, think how to write code that performs those same steps.

[jigglywiggly]

Oh I already know how recursively, it checks the two top elements a[0] and b[0], then if they are the same, it removes both. Then it goes to the next one, if the next two are NOT the same, and a[0] is bigger than b[0], remove b[0]. Then check again, is a[0] ==b[0]? If so remove both, then is b[0] > a[0]? If it is, then remove a[0].

[jigglywiggly]

Ok I think I made it recursively

 public int commonElementsRecursively( int a[], int b[]) {
     if ( a.length==1 || b.length ==1) {
          return counter; //I think this is the correct base case, I just learned recursion yesterday :(
     }
     else {
        if(a[0]==b[0]) {
         counter++;
         int[] v = new int[a.length-1];
         int[] n = new int[b.length-1];
         int counter2=0;
         int counter3=0;
         for(int i =1; i<a.length; i++) {
             v[counter2]=a[i];
             counter2++;

         }
         for(int j = 1; j<b.length; j++) {
             n[counter3]=b[j];
             counter3++;
         }
         return commonElementsRecursively(v, n);
        }

        if(a[0]>b[0]) {
      int[] v = new int[b.length-1];
         int counter2=0;
      for(int i=1; i<b.length; i++) {
          v[counter2]=b[i];
      }
      return(commonElementsRecursively(a,v));
        }
        if(b[0]>a[0]) {
            int[] v = new int[a.length-1];
            int counter3=0;
            for(int i =1; i<a.length; i++) {
                v[counter3]=a[i];

            }
            return(commonElementsRecursively(v,b));
        }
        
        return 1;

      
     }
     

    }

Also assume counter was made in the top of the class. (Initialized at 0)

However with this input in the main

        Lovelyness j = new Lovelyness();
        int[] a = new int[8];
        int[] b = new int[6];

           a[0]=1;
        a[1]=2;
        a[2]=2;
        a[3]=2;
        a[4]=5;
        a[5]=5;
        a[6]=6;
        a[7]=1;


        b[0]=1;
        b[1]=1;
        b[2]=1;//
        b[3]=2; //
        b[4]=5;//
        b[5]=2;//


        
       System.out.println(j.commonElementsRecursively(a, b)) ;

It spits out 2 :?, I think it should be 3.

EDIT: Wait don't look at this code I see obvious bugs, I will edit this again when it's ready :D

[JosAH]

Why not let the Collections framework do the nasty work?

Integer[] a= { 0, 1, 1, 2, 2, 2, 5, 6, 1 };
Integer[] b= { 0, 1, 1, 2, 5, 2 };
		
List<Integer> la= new ArrayList<Integer>(Arrays.asList(a));
List<Integer> lb= Arrays.asList(b);
		
la.retainAll(lb);
System.out.println(la);

kind regards,

Jos

[jigglywiggly]

Ok this I believe does work, I will test more inputs later :D

  public int commonElementsRecursively( int a[], int b[]) {
     if ( a.length==0 || b.length ==0) {
          return counter;
     }
     else {
        if(a[0]==b[0]) {
         counter++;
         int[] v = new int[a.length-1];
         int[] n = new int[b.length-1];
         int counter2=0;
         int counter3=0;
         for(int i =1; i<a.length; i++) {
             v[counter2]=a[i];
             counter2++;

         }
         for(int j = 1; j<b.length; j++) {
             n[counter3]=b[j];
             counter3++;
         }
         return commonElementsRecursively(v, n);
        }

        if(a[0]>b[0]) {
      int[] v = new int[b.length-1];
         int counter2=0;
      for(int i=1; i<b.length; i++) {
          v[counter2]=b[i];
          counter2++;
      }
      return(commonElementsRecursively(a,v));
        }
        if(b[0]>a[0]) {
            int[] v = new int[a.length-1];
            int counter3=0;
            for(int i =1; i<a.length; i++) {
                v[counter3]=a[i];
                 counter3++;
            }
            return(commonElementsRecursively(v,b));
        }
        
        return 1;

      
     }
     

    }

[xcallmejudasx]

I'm curious to the extent of your matching. assume

A = {0,1,2,3}
B = {1,1,1,1}

should this return showing there are 4 matches (the set B contains 4 instances of some element contained in A) or should it show 1 match(some element in set A is contained in set B, regardless of how many times it's in there)

Also what about

A = {1,1,2,3}
B = {1,1,1,1}

would this be 1, 2 or 8?

Maybe I just read over everything too fast but these rules need to be determined before you can properly return the number of matches.

[xcallmejudasx]

alright I just ran your algorithm a few times and determined some stuff.

a[0] = 1;
a[1] = 2;
a[2] = 2;
a[3] = 3;
a[4] = 4;

b[0] = 1;
b[1] = 1;
b[2] = 6;
b[3] = 7;
b[4] = 8;

returns 1 even though a[0] = b[0] and b[1], this means your algorithm doesn't respond to duplicates(which could be fine if that's what you're required to do) however if I remember anything from discrete math your answer should be 2(set B contains 2 instances of an element of set A)

[CodesAway]

alright I just ran your algorithm a few times and determined some stuff.

a[0] = 1;
a[1] = 2;
a[2] = 2;
a[3] = 3;
a[4] = 4;

b[0] = 1;
b[1] = 1;
b[2] = 6;
b[3] = 7;
b[4] = 8;

returns 1 even though a[0] = b[0] and b[1], this means your algorithm doesn't respond to duplicates(which could be fine if that's what you're required to do) however if I remember anything from discrete math your answer should be 2(set B contains 2 instances of an element of set A)

No, there's only 1 match. If 'a' had two values that equal 1, then it would be two (like in your previous post). Most instances of this algorithm work on this logic: If an element is in both lists, then the element exists in list1 and a corresponding element exists in list2.

For example, if the number one appears once in both lists, there is one match. If the numbered appeared twice in both lists, there would be two matches. It's the same rules for mastermind (a problem I saw a few days ago on this forum).