Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Java Arrays

  1. Nov 14, 2004 #1
    Hello all

    I am trying to write a program that checks whether one array is contained in another array. For example,

    A = {1,2,3}
    B= {1,2,3,4,5,6}

    A is contained in B, so we print out true, otherwise we print out false.

    Any advice or tips in writing this program would be greatly appreciated.

    Thanks!
     
  2. jcsd
  3. Nov 14, 2004 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    When you say "contains" do you mean simply that one array has the elements of the other? (e.g. {1, 2, 4} contains {4, 2}), or are you specifically requiring one to be a sublist of the other? (e.g. {1, 2, 3, 4} contains {1, 2, 3} but not {1, 3} or {3, 2, 1})
     
  4. Nov 14, 2004 #3
    No i mean that it can contain any of the elements:

    {1, 2, 4} contains {4, 2}

    This is correct

    Any help would be greatly appreciated

    Thanks a alot!
     
  5. Nov 14, 2004 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    (does {1, 2, 4} contain {4, 2, 2}?)


    Well, how would you do this by hand? And I don't mean on an easy example like this -- what if you had two arrays each with hundreds of elements! How would you do such a problem by hand?
     
  6. Nov 14, 2004 #5
    Actually, let's say we have

    A = {1,2,3,4} and B = {1,2,3,4,5}

    Then B contains A. In order for B to contain A all of the elements of A have to be in B in the exact same order.
     
  7. Nov 14, 2004 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Same question: suppose the arrays were hundreds long. How would you do it by hand?
     
  8. Nov 14, 2004 #7
    wouldnt you check whether the first n-1 elements of each array match each other?
     
  9. Nov 14, 2004 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, does {1, 2, 3, ..., 1000} contain {1, 2, 3}? What about {10, 11, 12}?
     
  10. Nov 14, 2004 #9
    yes, so would you loop through each array, and see whether an elements match. How would you do this?
     
  11. Nov 14, 2004 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You first figure out how to write clear, precise algorithm. It may seem laborious, but you have to do it anyways to write your program, so you might as well do it in a language you understand better.
     
  12. Nov 14, 2004 #11
    Here is what I did:

    First I need to declare the two arrays A and B.
    Then I write elements (integers) in the two array A and B.
    Go through all the elements of arrays A and B.
    If successive locations in the array have the same element return true. Print true.
    If not return false.
    Then print false.

    Would this be the basic algorithm in trying to write this program?
     
  13. Nov 15, 2004 #12
    What you are trying to do is find a substring within a string. There are a couple algorithms that can accomplish this.

    There is an very easy, two loop, O(mn) algorithm that can do it (where m,n are the size of your arrays).

    There is a smarter algorithm that skips ahead in the loop giving you better running time.

    There is a O(n) worst case algorithm that requires the use of trees.
     
  14. Nov 15, 2004 #13
    what do you mean by an O(mn) algorithm? I am just learning ( in middle school). Can you please be more specific?

    Thanks
     
  15. Nov 15, 2004 #14
    Oh, well in that case don't worry about O(n) stuff yet, unless you have at least algebra behind you.

    I just realized that the problem is a little bit different than substring within a string. That is actually harder to do. Given your example, order and duplicates do not matter. In other words if { 1, 2, 3} contains {2, 3, 2, 3} ? This is quite easy to do:

    for each element in B
    scan to see if the element is in A

    Write the code in your language of choice and I'll critique it.
     
  16. Nov 15, 2004 #15
    Okay, it seems that I'm confused on the specifics... Does order matter? If so, it's really easy. If not, it's not so easy, but still easy.

    Hint, just in case you need it: Java arrays can tell you how long they are.

    if you have an array a = {1,2,3,4}, you can see how long it is by saying a.length. You may or may not need this, depending on the specifics of the assignment.

    You will definitely need at least one "for" loop, though.
     
  17. Nov 15, 2004 #16
    Code (Text):
     boolean exsist = false;

    for(i=0;i<a.length;i++)  //loop through your a array
    {
      exsist = false; //set the flag equal to false. Do it hear because we want to see if that particular element is in the 2nd array
       for(j=0;j<b.length;j++)
       {
        if( a.get(i) == b.get(j) )
        {  
          //if a is in b then set to true and break out of the loop cause no reason to finish
          exsist = true;
          break;
        }
       } //end 2nd array for
      if(exsist == false)
      {  
       if we get hear that means the previuos element wasn't in the array, so the hole thing sucks and it's a bust. so might as well break out of the loop
       break;
      }
    }

    if(exsist == true)
    system.out.print(" all of A's elements are in array B");
     
  18. Nov 15, 2004 #17
    Looks like it would work to me.
     
  19. Nov 15, 2004 #18
    Why isnt my code working? It says variable i is not defined.

    Code (Text):
     public class check
    {
        public boolean isDifferent(int [] a, int [] b)
        {

        boolean exsist = false;

        for(i=0; i < a.length; i++)  //loop through your a array
        {
        exsist = false;
        for(j=0;j<b.length;j++)
       {
        if( a.get(i) == b.get(j) )
        {  
         
          exsist = true;
          break;
        }
      }
      if(exsist == false)
      {  
       
       break;
      }
    }

    if(exsist == true)
    system.out.print(" all of A's elements are in array B");
        }
    }
     
     
  20. Nov 15, 2004 #19

    graphic7

    User Avatar
    Gold Member

    You need to define a datatype for 'i'. Decide whether it is an integer, double, float, string, etc and declare it.
     
  21. Nov 15, 2004 #20
    what about a.length? Why does it say its not defined?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Java Arrays
  1. Big arrays (Replies: 13)

  2. Java help (Replies: 15)

  3. Java q (Replies: 3)

  4. Java problem. (Replies: 4)

Loading...