Java Arrays

  • #1
1,235
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!
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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})
 
  • #3
1,235
1
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!
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
(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?
 
  • #5
1,235
1
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.
 
  • #6
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Same question: suppose the arrays were hundreds long. How would you do it by hand?
 
  • #7
1,235
1
wouldnt you check whether the first n-1 elements of each array match each other?
 
  • #8
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Well, does {1, 2, 3, ..., 1000} contain {1, 2, 3}? What about {10, 11, 12}?
 
  • #9
1,235
1
yes, so would you loop through each array, and see whether an elements match. How would you do this?
 
  • #10
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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.
 
  • #11
1,235
1
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?
 
  • #12
294
0
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.
 
  • #13
1,235
1
what do you mean by an O(mn) algorithm? I am just learning ( in middle school). Can you please be more specific?

Thanks
 
  • #14
294
0
courtrigrad said:
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.
 
  • #15
23
0
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.
 
  • #16
1,235
1
Code:
 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");
 
  • #17
23
0
Looks like it would work to me.
 
  • #18
1,235
1
Why isnt my code working? It says variable i is not defined.

Code:
 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");
    }
}
 
  • #19
graphic7
Gold Member
450
2
You need to define a datatype for 'i'. Decide whether it is an integer, double, float, string, etc and declare it.
 
  • #20
1,235
1
what about a.length? Why does it say its not defined?
 
  • #21
551
1
courtrigrad said:
what about a.length? Why does it say its not defined?
It should be a.length() (similarly, b.length()).
 
  • #22
437
1
Let me ask something. I didn't know that we can write a.get( index ). Doesn't Java allow the use of a[ index ]?
 
  • #23
551
1
ramollari said:
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.
 

Related Threads on Java Arrays

  • Last Post
Replies
4
Views
16K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
6
Views
28K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
13
Views
6K
  • Last Post
6
Replies
129
Views
21K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
11
Views
9K
  • Last Post
Replies
6
Views
1K
Top