Checking if One Array is Contained in Another using Java Arrays

[courtrigrad]

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!

 

[Hurkyl]

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})

 

[courtrigrad]

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 a lot!

 

[Hurkyl]

(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?

 

[courtrigrad]

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.

 

[Hurkyl]

Same question: suppose the arrays were hundreds long. How would you do it by hand?

 

[courtrigrad]

wouldnt you check whether the first n-1 elements of each array match each other?

 

[Hurkyl]

Well, does {1, 2, 3, ..., 1000} contain {1, 2, 3}? What about {10, 11, 12}?

 

[courtrigrad]

yes, so would you loop through each array, and see whether an elements match. How would you do this?

 

[Hurkyl]

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.

 

[courtrigrad]

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?

 

[so-crates]

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.

 

[courtrigrad]

what do you mean by an O(mn) algorithm? I am just learning ( in middle school). Can you please be more specific?

Thanks

 

[so-crates]

what do you mean by an O(mn) algorithm? I am just learning ( in middle school). Can you please be more specific?

Thanks

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.

 

[The Idiot]

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.

 

[courtrigrad]

 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");

 

[The Idiot]

Looks like it would work to me.

 

[courtrigrad]

Why isn't my code working? It says variable i is not defined.

 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");
    }
}

 

[graphic7]

You need to define a datatype for 'i'. Decide whether it is an integer, double, float, string, etc and declare it.

 

[courtrigrad]

what about a.length? Why does it say its not defined?

 

[Nylex]

what about a.length? Why does it say its not defined?

It should be a.length() (similarly, b.length()).

 

[ramollari]

Let me ask something. I didn't know that we can write a.get( index ). Doesn't Java allow the use of a[ index ]?

 

[Nylex]

Let me ask something. I didn't know that we can write a.get( index ). Doesn't Java allow the use of a[ index ]?

I didn't know about being able to write a.get(index) either, but yes, Java does allow you to use a[index] if you want the value stored at that index position.