Intersections & Unions

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

30 Replies - 8012 Views - Last Post: 01 April 2011 - 08:33 AM Rate Topic: -----

#1 KeithStone  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 50
  • Joined: 29-March 11

Intersections & Unions

Posted 29 March 2011 - 09:02 PM

I need to write a program that outputs the intersection and union of 2 set inputs, up to 500 numbers. Here's where I'm running into an issue, I can't use any set classes.

So, for example:

Input:
Please enter set 1:
1 3 5 7 9
Please enter set 2:
2 4 6 8

Output:
Intersection:
Union: 1 2 3 4 5 6 7 8 9

Example #2

Input:
Please enter set 1:
1 3 5
Please enter set 2:
1 3 8

Output:
Intersection: 1 3
Union: 1 3 5 8

I'm confused at where to start and I know you guys frown on that, but can someone give me a hand at where to start?
Obviously, I have to start with scanner to read in the information.

Is This A Good Question/Topic? 0
  • +

Replies To: Intersections & Unions

#2 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10396
  • View blog
  • Posts: 38,464
  • Joined: 27-December 08

Re: Intersections & Unions

Posted 29 March 2011 - 09:14 PM

Take a look at using Sets here. Intersection is pretty easy, since the Set interface has an addAll() method. Unions are a little different. Take the smaller of the two Sets. For each element in the first Set that is in the second, add it to a third result Set.
Was This Post Helpful? 0
  • +
  • -

#3 KeithStone  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 50
  • Joined: 29-March 11

Re: Intersections & Unions

Posted 29 March 2011 - 09:26 PM

View PostKeithStone, on 29 March 2011 - 09:02 PM, said:

I can't use any set classes.

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10396
  • View blog
  • Posts: 38,464
  • Joined: 27-December 08

Re: Intersections & Unions

Posted 29 March 2011 - 09:29 PM

Sorry, I missed that. :)

You can still do that with ArrayList. Same concept, and basically the same methods.
Was This Post Helpful? 0
  • +
  • -

#5 KeithStone  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 50
  • Joined: 29-March 11

Re: Intersections & Unions

Posted 30 March 2011 - 06:02 PM

I have made it this far:


import java.util.Scanner;

public class Test
{
	public static void main (String[] args)
	{
		
		Scanner scan = new Scanner( System.in );
		int[] array1 = new int[100];
		int[] array2 = new int [100];	
		
		for( int i = 0; i < array1.length; i++ )
		{
			System.out.println("First set ending in -1");
			array1[i] = scan.nextInt( );
		for( int j = 0; j < array2.length; j++ )
		{
			System.out.println("Second set ending in -1");
			array2[j] = scan.nextInt();
		
		if( array1[i] == array2[j] )
			System.out.println("Intersection at: " + array1[i] );
	    if(array1[i] != array2[j]) 
				System.out.println("Intersection at: ");
		}
		}
		}
	}



My output isn't correct though.
Example input: 1 3 5 7 9 gives me:
Second set ending in -1
Intersection at:
Second set ending in -1
Intersection at:
Second set ending in -1
Intersection at:
Second set ending in -1
Intersection at:
Second set ending in -1


But, if I only enter one number, say 5 for both, I get:
First set ending in -1
5
Second set ending in -1
5
Intersection at: 5
Second set ending in -1

Can you help me understand what I'm doing incorrectly?

Edited by macosxnerd101: Please, :code:.
Was This Post Helpful? 0
  • +
  • -

#6 KeithStone  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 50
  • Joined: 29-March 11

Re: Intersections & Unions

Posted 30 March 2011 - 06:08 PM

Quote

Edited by macosxnerd101: Please, :code:.


I had originally screwed up and used [\code] but edited the post.

This post has been edited by KeithStone: 30 March 2011 - 06:08 PM

Was This Post Helpful? 0
  • +
  • -

#7 KeithStone  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 50
  • Joined: 29-March 11

Re: Intersections & Unions

Posted 30 March 2011 - 08:39 PM

Can anyone help me out with this?
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10396
  • View blog
  • Posts: 38,464
  • Joined: 27-December 08

Re: Intersections & Unions

Posted 30 March 2011 - 08:52 PM

You posted your code only a few hours ago. Seriously, be patient. Most questions are answered within 48 hours, and usually less than that. :)

Check your input loop. Your loop for getting the second set input is within the loop for getting the input for the first set.

Also, using an ArrayList over an array will make your life a lot easier. It's a List, not a Set, so you should be good in terms of staying within the guidelines. Methods like retainAll() make intersections so easy to detect. And the add() method makes unions a lot easier as well, since you can modify the List structure.
Was This Post Helpful? 0
  • +
  • -

#9 KeithStone  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 50
  • Joined: 29-March 11

Re: Intersections & Unions

Posted 30 March 2011 - 09:23 PM

I'm not following you - how do I use a an ArrayList with scanner?
Do you have an example of some code that I can look at?
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10396
  • View blog
  • Posts: 38,464
  • Joined: 27-December 08

Re: Intersections & Unions

Posted 30 March 2011 - 09:26 PM

Locke has a tutorial on ArrayLists vs. Static Arrays that you might find helpful. Also check out the documentation.
Was This Post Helpful? 0
  • +
  • -

#11 KeithStone  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 50
  • Joined: 29-March 11

Re: Intersections & Unions

Posted 30 March 2011 - 10:24 PM

I came up with this, but I don't think I'm on the right track.

 
import java.util.*;
public class Test2{
	public static void main(String[]args){
		List a = new ArrayList();
		Scanner input=new Scanner(System.in);
		System.out.println("Enter first set: ");
		for(int i=0;i < 5;i++){
			String st=input.next();
			a.add(st);	
		}
		List b = new ArrayList();
		System.out.println("Enter second set: ");
		for(int i=0;i < 5;i++){
			String st=input.next();
			b.add(st);	
		}
		}


Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10396
  • View blog
  • Posts: 38,464
  • Joined: 27-December 08

Re: Intersections & Unions

Posted 31 March 2011 - 04:11 AM

Java Collections are generic. So you should be storing a List<Integer> or List<String> if you want your ArrayList to be storing Integers or Strings respectively. You should not be storing just a plain List.

You're on the right track, though.
Was This Post Helpful? 0
  • +
  • -

#13 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1940
  • View blog
  • Posts: 4,027
  • Joined: 11-December 07

Re: Intersections & Unions

Posted 31 March 2011 - 04:41 AM

Dude, he needs help on writing an algorithm, not a lesson on data structures.

Union

Basically you want to join the two sets together but make sure you don't have any duplicates. Here's an easy description of how to do it:

1. Create a new set for the union.
2. Add all of the first set to it.
3. Take each item in the second set in turn.
4. Check to see if it is in the first set.
5. Add it to the union set if it is not in the first set.

Intersection

Here you are looking for items that appear in both sets.

1. Create an intersection set.
2. Take each item in the first set in turn.
3. Check to see if it is in the second set.
4. Add it to the intersection if it is in the second set.

Step 4 for the union and step 3 in the intersection are the same and will require a few lines of code. I suggest combining them into a method that returns a boolean.

Have a shot at coding these and we can look at your code then.

Since you're finding this difficult, choose whatever data structure you are most comfortable with. Arrays, ArrayLists, Vectors, LinkedLists and Queues are all fine. You can do this with any of them.

I also suggest that to begin with you hard code a couple of sets. You are almost there with your user entry... but that is the icing on the cake. Get the important stuff done first.

This post has been edited by cfoley: 31 March 2011 - 04:42 AM

Was This Post Helpful? 3
  • +
  • -

#14 KeithStone  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 50
  • Joined: 29-March 11

Re: Intersections & Unions

Posted 31 March 2011 - 09:07 PM

Can someone just explain to me how I can get the loop to turn off in this code? I'm not wrapping my head around this.


import java.util.Scanner;

public class Test
{
	public static void main (String[] args)
	{
		
		Scanner scan = new Scanner( System.in );
		int[] array1 = new int[100];
		int[] array2 = new int [100];	
		
		for( int i = 0; i < array1.length; i++ )
		{
			System.out.println("First set ending in -1");
			array1[i] = scan.nextInt( );
		for( int j = 0; j < array2.length; j++ )
		{
			System.out.println("Second set ending in -1");
			array2[j] = scan.nextInt();
		
		if( array1[i] == array2[j] )
			System.out.println("Intersection at: " + array1[i] );
	    if(array1[i] != array2[j]) 
				System.out.println("Intersection at: ");
		}
		}
		}
	}


Was This Post Helpful? 0
  • +
  • -

#15 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10396
  • View blog
  • Posts: 38,464
  • Joined: 27-December 08

Re: Intersections & Unions

Posted 31 March 2011 - 09:13 PM

You want to check for unions and intersections after you populate your arrays. You shouldn't need nested loops initially to populate your arrays. Here's the logic you want to incorporate:
for(int i = 0; i < myArr.length; i++){
    //get input
    //if the input is -1, break
    //otherwise, assign it to myArr[i]
}
for(int i = 0; i < myArr2.length; i++){
    //same process for getting input and 
    //assigning it to myArr2's elements
}

//Now that we have user input
//let's look at performing our 
//union and intersection



Quote

Dude, he needs help on writing an algorithm, not a lesson on data structures.

It's just easier to do this with ArrayLists because of the built in functionality.
Was This Post Helpful? 1
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3