Results 1 to 12 of 12
  1. #1
    jigglywiggly is offline Senior Member
    Join Date
    Nov 2008
    Posts
    105
    Rep Power
    0

    Default Simple array comparison

    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
    Java 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
    Java Code:
            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...

  2. #2
    CodesAway's Avatar
    CodesAway is offline Senior Member
    Join Date
    Sep 2009
    Location
    Texas
    Posts
    238
    Rep Power
    5

    Default

    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?

    Java Code:
    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?
    Last edited by CodesAway; 11-11-2009 at 05:45 AM.
    CodesAway - codesaway.info
    writing tools that make writing code a little easier

  3. #3
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    Quote Originally Posted by CodesAway View Post
    Let me clarify the goal....
    I think that the original poster (OP) needs to clarify this. To the OP: please post your assignment verbatim.

  4. #4
    jigglywiggly is offline Senior Member
    Join Date
    Nov 2008
    Posts
    105
    Rep Power
    0

    Default

    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?

  5. #5
    CodesAway's Avatar
    CodesAway is offline Senior Member
    Join Date
    Sep 2009
    Location
    Texas
    Posts
    238
    Rep Power
    5

    Default

    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.

    Java Code:
    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.
    CodesAway - codesaway.info
    writing tools that make writing code a little easier

  6. #6
    jigglywiggly is offline Senior Member
    Join Date
    Nov 2008
    Posts
    105
    Rep Power
    0

    Default

    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].

  7. #7
    jigglywiggly is offline Senior Member
    Join Date
    Nov 2008
    Posts
    105
    Rep Power
    0

    Default

    Ok I think I made it recursively
    Java Code:
     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
    Java Code:
            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
    Last edited by jigglywiggly; 11-11-2009 at 08:19 PM.

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,519
    Blog Entries
    7
    Rep Power
    20

    Default

    Why not let the Collections framework do the nasty work?

    Java Code:
    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

  9. #9
    jigglywiggly is offline Senior Member
    Join Date
    Nov 2008
    Posts
    105
    Rep Power
    0

    Default

    Ok this I believe does work, I will test more inputs later :D
    Java Code:
      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;
    
          
         }
         
    
        }

  10. #10
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    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.
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  11. #11
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    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)
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  12. #12
    CodesAway's Avatar
    CodesAway is offline Senior Member
    Join Date
    Sep 2009
    Location
    Texas
    Posts
    238
    Rep Power
    5

    Default

    Quote Originally Posted by xcallmejudasx View Post
    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).
    Last edited by CodesAway; 11-12-2009 at 01:32 AM.
    CodesAway - codesaway.info
    writing tools that make writing code a little easier

Similar Threads

  1. Two simple array problems.
    By DMiller in forum New To Java
    Replies: 4
    Last Post: 11-06-2009, 11:50 AM
  2. My Simple Array Does Not Work!
    By Simplev_v in forum New To Java
    Replies: 16
    Last Post: 09-07-2009, 02:43 PM
  3. Replies: 5
    Last Post: 02-25-2009, 07:14 PM
  4. Simple array questions
    By jigglywiggly in forum New To Java
    Replies: 6
    Last Post: 02-15-2009, 05:57 AM
  5. Ip adresses comparison
    By ModestUrgell in forum New To Java
    Replies: 0
    Last Post: 05-30-2008, 12:13 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •