Check if array contains array

  • (2 Pages)
  • +
  • 1
  • 2

19 Replies - 3065 Views - Last Post: 14 August 2010 - 11:50 AM Rate Topic: -----

#1 Guest_nub*


Reputation:

Check if array contains array

Posted 13 August 2010 - 03:38 PM

I am trying to check if an array's elements contain another array.
For example array a contains array b. This would return true:
		int[] a = {1,2,3,4,5};
		int[] b = {2,3,4};


This would be false:
		int[] a = {1,2,4,5,6};
		int[] b = {2,3,4};



preferably, I would like to do this without a loop since my arrays are very large and it takes too long.

Is This A Good Question/Topic? 0

Replies To: Check if array contains array

#2 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Check if array contains array

Posted 13 August 2010 - 03:45 PM

so basically you are trying to find if elements of array b exist in array a. a simple nested loop will do this
Was This Post Helpful? 0
  • +
  • -

#3 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Check if array contains array

Posted 13 August 2010 - 03:45 PM

View Postnub, on 13 August 2010 - 02:38 PM, said:

I am trying to check if an array's elements contain another array.
For example array a contains array b. This would return true:

Pardon me, you misworded your desire in relation to your example. Not contains an array, you meant contains the elements in the array...huge difference.

As for not using loops to accomplish your task, it would be hard, if at all possible. I personally can't think of a way to do that without using loops. You can either loop through the 2nd array and check to see if the 1st array contains it by looping through. Or you could use the better method in the Arrays class, binarySearch.
Arrays.sort(your1stArray);
for(int i : your2ndArray)
{ 
  if(Arrays.binarySearch(your1stArray,i) < 0)
  {
    return false;
  }
}
return true;



Edit: Mosty keeps me on my toes :bananaman: Must sort the 1st array.

This post has been edited by bcranger: 13 August 2010 - 03:57 PM

Was This Post Helpful? 0
  • +
  • -

#4 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Check if array contains array

Posted 13 August 2010 - 03:48 PM

@bcranger you need to sort the array first, if you're using binary search
Was This Post Helpful? 1
  • +
  • -

#5 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Check if array contains array

Posted 13 August 2010 - 03:55 PM

Yea, you are right mostyfriend :D, my bad missed that point :(
Was This Post Helpful? 0
  • +
  • -

#6 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Check if array contains array

Posted 13 August 2010 - 04:37 PM

lol, it happens to the best of us.
Was This Post Helpful? 0
  • +
  • -

#7 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Check if array contains array

Posted 13 August 2010 - 09:03 PM

View Postnub, on 13 August 2010 - 04:38 PM, said:

preferably, I would like to do this without a loop since my arrays are very large and it takes too long.

What ??? If you arrays are large you want to use a loop
Was This Post Helpful? 0
  • +
  • -

#8 Guest_nub*


Reputation:

Re: Check if array contains array

Posted 14 August 2010 - 08:59 AM

View Postpbl, on 13 August 2010 - 08:03 PM, said:

View Postnub, on 13 August 2010 - 04:38 PM, said:

preferably, I would like to do this without a loop since my arrays are very large and it takes too long.

What ??? If you arrays are large you want to use a loop

Well if java already has a method that does this I would prefer to use that.

I am working on my loop. Having some difficulties:
	public boolean compare(int[] a, int[]B)/>{
		for(int i=0; i<a.length;i++){
			if(a[i] == b[0]){
				int count = 0;
				for(int j = 0; j<b.length; j++){
					if(a[i+j] == b[j]){
						count++;
						}
					if(count == b.length){
						return true;
					}else{
						count =0;
					}
				}
			}
		}
		return false;
	}


Was This Post Helpful? 0

#9 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Check if array contains array

Posted 14 August 2010 - 09:01 AM

OP: I already showed you how to do it, although I think it seems very inefficient :)
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10658
  • View blog
  • Posts: 39,571
  • Joined: 27-December 08

Re: Check if array contains array

Posted 14 August 2010 - 09:03 AM

You are taking the wrong approach. Take the smaller array and iterate through the bigger array. If you reach an index where the smallerArray.length exceeds the number of remaining elems in the larger array, return false. Otherwise, iterate linearly through the bigger array, comparing the corresponding element in the smaller array. If you find elems that don't match, reset the smallerArray counter to 0 (or start over with the smaller array).

Edit: @bcranger: If the OP is concerned about the ordering of the elements, sorting is a moot point. :)
Was This Post Helpful? 0
  • +
  • -

#11 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Check if array contains array

Posted 14 August 2010 - 09:18 AM

View Postmacosxnerd101, on 14 August 2010 - 08:03 AM, said:

You are taking the wrong approach. Take the smaller array and iterate through the bigger array. If you reach an index where the smallerArray.length exceeds the number of remaining elems in the larger array, return false. Otherwise, iterate linearly through the bigger array, comparing the corresponding element in the smaller array. If you find elems that don't match, reset the smallerArray counter to 0 (or start over with the smaller array).

Edit: @bcranger: If the OP is concerned about the ordering of the elements, sorting is a moot point. :)

Have to sort to use the binary search method or result will be messed up. Mostyfriendman kindly pointed that out :)
Was This Post Helpful? 0
  • +
  • -

#12 Guest_nub*


Reputation:

Re: Check if array contains array

Posted 14 August 2010 - 09:30 AM

bcranger's method works for my smaller example but what about this example:

import java.awt.image.BufferedImage;
import java.awt.image.PixelGrabber;
import java.io.File;
import java.io.IOException;
import java.util.Arrays;

import javax.imageio.ImageIO;

public class Main {
	public int[] pixels(BufferedImage image) {
		PixelGrabber grabber;
		int[] pixels = new int[image.getWidth() * image.getHeight()];
		try {
			grabber = new PixelGrabber(image, 0, 0, image.getWidth(),
					image.getHeight(), pixels, 0, image.getWidth());
			grabber.grabPixels(0);

		} catch (Exception e) {
			e.printStackTrace();
		}
		return pixels;
	}

	public void program() {
		BufferedImage image = null;
		BufferedImage image2 = null;
		try {
			image = ImageIO.read(new File("1.jpg"));
		} catch (IOException e) {
		}
		try {
			image2 = ImageIO.read(new File("2.jpg"));
		} catch (IOException e) {
		}
		int[] a = pixels(image);
		int[] b = pixels(image2);
		System.out.println(Boolean.toString(compare(a, B)/>));
	}

	public boolean compare(int[] a, int[] B)/> {
		Arrays.sort(a);
		for (int i : B)/> {
			if (Arrays.binarySearch(a, i) < 0) {
				return false;
			}
		}
		return true;

	}

	public static void main(String[] args) {
		Main main = new Main();
		main.program();

	}
}



The second image is a cropped version of the first image.

Posted Image
Posted Image
Was This Post Helpful? 0

#13 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Check if array contains array

Posted 14 August 2010 - 09:36 AM

Should be false. The blue color looks different in the two pictures. You wanted the method to return true if ALL the array values were contained, right?
Was This Post Helpful? 0
  • +
  • -

#14 Guest_nub*


Reputation:

Re: Check if array contains array

Posted 14 August 2010 - 09:42 AM

View Postbcranger, on 14 August 2010 - 08:36 AM, said:

Should be false. The blue color looks different in the two pictures. You wanted the method to return true if ALL the array values were contained, right?

Yes thats correct. I will try to find some identical pictures
Was This Post Helpful? 0

#15 Guest_nub*


Reputation:

Re: Check if array contains array

Posted 14 August 2010 - 09:47 AM

Posted Image
Posted Image

I used these pictures and it still returned false. This should be true, correct?
Was This Post Helpful? 0

  • (2 Pages)
  • +
  • 1
  • 2